#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
struct edge
{int adv,w,next;};
const int N=1000,T=12;
edge es[N*N];
int n,m,t,g[N],e;
inline void addedge(int a,int b,int w)
{
	es[++e].adv=b;
	es[e].w=w;
	es[e].next=g[a];
	g[a]=e;
}
void init()
{
	scanf("%d%d%d",&n,&m,&t);
	memset(g,0,sizeof(g));e=0;
	int a,b,c;
	while (m--)
	{
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
		addedge(b,a,c);
	}
}
struct node
{
	int x,y,w;
	node(){}
	node(const int &_x,const int &_y,const int &_w):
	x(_x),y(_y),w(_w){}
	bool operator<(const node& t)const
	{return w>t.w;}
};
priority_queue<node> q;
bool flag[T][N];
int dis[T][N];
void slove()
{
	memset(dis,0x3f,sizeof(dis));
	dis[0][0]=0;
	q.push(node(0,0,0));
	memset(flag,0,sizeof(flag));
	node u;
	int i,j,dt;
	while (!q.empty())
	{
		u=q.top();q.pop();
		if (u.x>10||flag[u.x][u.y]) continue;
		dis[u.x][u.y]=u.w;
		flag[u.x][u.y]=1;
		i=u.y;
		for (j=g[i];j;j=es[j].next)
			if ((dt=dis[u.x][u.y]+es[j].w)<dis[u.x+1][es[j].adv])
			{
				dis[u.x+1][es[j].adv]=dt;
				q.push(node(u.x+1,es[j].adv,dt));
			}
	}
	int ans=0x3f3f3f3f;
	for (i=0;i<=10;++i)
		ans=min(ans,dis[i][t]);
	printf("%d\n",ans);
}
int main()
{
freopen("ping.in","r",stdin);
freopen("ping.out","w",stdout);
    init();
    slove();
    return 0;
}