1 /*  2  * Author:  Yzcstc  3  * Created Time:  2014/11/5 19:25:47  4  * File Name: revamp.cpp  5  */  6 #include<cstdio>  7 #include<iostream>  8 #include<cstring>  9 #include<cstdlib> 10 #include<cmath> 11 #include<algorithm> 12 #include<string> 13 #include<map> 14 #include<set> 15 #include<vector> 16 #include<queue> 17 #include<stack> 18 #include<ctime> 19 #define M0(x)  memset(x, 0, sizeof(int) * (n+10)) 20 #define MP make_pair 21 #define x first 22 #define y second 23 using namespace std; 24 typedef long long ll; 25 typedef pair<ll, int> pii; 26 const int maxn = 1200000; 27 struct edge{ 28     int v, w, next;      29 } e[maxn * 5]; 30 int last[maxn], tot; 31 int n, k, m; 32  33 void add(const int &u,const int &v, const int& w){ 34      e[tot] = (edge){v, w, last[u]}; last[u] = tot++; 35 } 36       37 void init(){ 38      int u, v, w; 39      memset(last, -1, sizeof(int) * (n * k + 10)); 40      tot = 0; 41      for (int i = 0; i < m; ++i){ 42           scanf("%d%d%d", &u, &v, &w); 43           add(u, v, w); add(v, u, w); 44           for (int i = 1; i <= k; ++i){ 45                add(u + i * n, v + i * n, w); 46                add(v + i * n, u + i * n, w);  47                add(u + (i-1) * n, v + i * n, 0); 48                add(v + (i-1) * n, u + i * n, 0); 49           } 50      } 51 } 52  53 ll dis[maxn]; 54 int vis[maxn]; 55 void dij(){ 56      priority_queue<pii, vector<pii>, greater<pii> > q; 57      int nt = n * k + n; 58      memset(vis, 0, sizeof(vis)); 59      for (int i = 1; i <= nt; ++i) dis[i] = (1LL<<50);  60      pii tmp(0, 1); dis[1] = 0; 61      q.push(tmp); 62      int u, v; 63      while (!q.empty()){ 64           u = q.top().y; 65           q.pop(); 66           if (vis[u]) continue; 67           vis[u] = 1; 68           for (int p = last[u]; ~p; p = e[p].next){ 69                v = e[p].v; 70                if (dis[u] + e[p].w < dis[v]){ 71                     dis[v] = dis[u] + e[p].w; 72                     tmp.x = dis[v], tmp.y = v; 73                     q.push(tmp);          74                }     75           }             76      } 77 } 78  79  80 void solve(){ 81      dij(); 82      ll ans = 1LL<<50; 83      for (int i = 0; i <= k; ++i) 84         ans = min(ans, dis[n+i*n]); 85      cout << ans << endl; 86 } 87  88 int main(){ 89     freopen("a.in", "r", stdin); 90     freopen("a.out", "w", stdout); 91     clock_t start, finish; 92     start = clock(); 93     while (scanf("%d%d%d", &n, &m, &k) != EOF){ 94          init(); 95          solve(); 96     } 97     finish = clock(); 98     double t = (double)(finish - start) / CLOCKS_PER_SEC; 99 //    printf("time = %.6f\n", t);100     return 0;101 }