记录编号	39032	评测结果	AAAAAAAAAA
题目名称	旅行	最终得分	100
用户昵称	ZhouHang	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2012-07-03 16:40:12	内存使用	9.52 MiB

/**
*Prob	: travela
*Data	: 2012-7-3
*Sol	: Floyd+spfa
*/

#include <cstdio>
#include <cstring>
#include <algorithm>

#define MaxN 120
#define MaxK 20
#define MaxList 1200000
#define oo 1000000000

using namespace std;

struct node {
	int n,k;
} list[MaxList];

int n,k;
int a[MaxN][MaxN];
int dis[MaxN][MaxK];
bool map[MaxN][MaxN];

void Floyd()
{
	for (int k=0; k<n; k++)
	 for (int i=0; i<n; i++)
	  for (int j=0; j<n; j++)
	  {
		if (k==i||k==j||i==j) continue;
		if (map[i][k]&&map[k][j])
			map[i][j] = map[i][j] || true;
	  }
}

void Spfa()
{
	bool v[MaxN][MaxK];
	memset(v,false,sizeof(v));
	v[0][0] = true; 
	list[1].n = list[1].k = 0;
	int open = 1,closd = 0;
	for (int i=0; i<n; i++)
	 for (int j=0; j<=k; j++)
		dis[i][j] = oo;
	dis[0][0] = 0;
	
	while (closd<open) {
		int nown = list[++closd].n;
		int nowk = list[closd].k;
		v[nown][nowk] = false;
		for (int tn=0; tn<n; tn++) {
			//????
			if (map[nown][tn]&&map[tn][nown]) {
				//?б?
				if (a[nown][tn])
					if (dis[nown][nowk]+a[nown][tn]<dis[tn][nowk]) {
						dis[tn][nowk] = dis[nown][nowk]+a[nown][tn];
						if (!v[tn][nowk]) {
							v[tn][nowk] = true;
							list[++open].n = tn;
							list[open].k = nowk;
						}
					}
			}
			//??????
			if (map[nown][tn]&&(!map[tn][nown])) {
				if (nowk == k) break;
				//?б?
				if (a[nown][tn])
					if (dis[nown][nowk]+2*a[nown][tn]<dis[tn][nowk+1]) {
						dis[tn][nowk+1] = dis[nown][nowk]+2*a[nown][tn];
						if (!v[tn][nowk+1]) {
							v[tn][nowk+1] = true;
							list[++open].n = tn;
							list[open].k = nowk+1;
						}
					}
			}
		}
		
	}
}

int main()
{
	freopen("travela.in","r",stdin);
	freopen("travela.out","w",stdout);
	
	int m,x,y,z;
	

	scanf("%d%d%d",&n,&m,&k);
	
	while (!(n==0&&m==0&&k==0)) {
	
	memset(map,false,sizeof(map));
	for (int i=0; i<n; i++)
	 for (int j=0; j<n; j++)
		a[i][j] = oo;
	for (int i=1; i<=m; i++) {
		scanf("%d%d%d",&x,&y,&z);
		a[x][y] = min(z,a[x][y]);
		map[x][y] = true;
	}
	
	Floyd();
	
	Spfa();
	
	int ans = oo;
	for (int i=0; i<=k; i++)
		ans = min(ans,dis[n-1][i]);
	
	if (ans==oo) ans = -1;
	
	printf("%d\n",ans);
	
	scanf("%d%d%d",&n,&m,&k);
	}
	
	fclose(stdin); fclose(stdout);
	return 0;
}