1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <string>
10 #include <math.h>
11 #include <stdlib.h>
12 #include <time.h>
13 using namespace std;
14 
15 const int LEN = 51;
16 typedef long long ll;
17 const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
18 int n, h, k;
19 
20 
21 void debug(ll Mix[][LEN]){
22     for(int i=0; i<n; i++){
23         for(int j=0; j<n; j++){
24             if(Mix[i][j] != LINF)cout << Mix[i][j] << ‘ ‘ ;
25             else cout << "- "; 
26         }
27         cout << endl;
28     }cout << endl;
29 }
30 
31 void Mul(ll a[][LEN], ll b[][LEN]){
32     ll c[LEN][LEN];
33     memset(c, 0x3f, sizeof c);
34     for(int i=0; i<n; i++){
35         for(int j=0; j<n; j++){
36             for(int k=0; k<n; k++){
37                 if(a[i][k] == LINF || b[k][j] == LINF) continue;
38                 c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
39             }
40         }
41     }
42 //    debug(a); debug(b);debug(c);
43     for(int i=0; i<n; i++){
44         for(int j=0; j<n; j++){
45             a[i][j] = c[i][j];
46         }
47     }
48 }
49 
50 void Mksm(ll t[][LEN], int k){
51     ll Mix[LEN][LEN];
52     for(int i=0; i<n; i++)
53         for(int j=0; j<n; j++)
54             Mix[i][j] = (i==j ? 0 : LINF);
55     while(k){
56         if(k & 1) Mul(Mix, t);
57         Mul(t, t);
58         k >>= 1;
59     }
60     for(int i=0; i<n; i++)
61         for(int j=0; j<n; j++)
62             t[i][j] = Mix[i][j];
63 }
64 
65 
66 int main()
67 {
68    // freopen("in.txt","r",stdin);
69     //freopen("out.txt","w",stdout);
70     
71     int T, a, b, val;
72     ll Mix[LEN][LEN];
73     cin >> T;
74     while(T--){
75         memset(Mix, 0x3f, sizeof Mix);
76         cin >> n >> h >> k;
77         for(int i=0; i<h; i++){
78             cin >> a >> b >> val;
79             a--, b--;
80             Mix[a][b] = val;        
81         }
82         Mksm(Mix, k);
83         if(Mix[0][n-1] != LINF) cout << Mix[0][n-1] << endl;
84         else cout << -1 << endl;
85     }
86     return 0;
87 }