#include using namespace std; struct edge {int /*from**/to,cost;}; typedef long long ll; typedef pair P; typedef vector VI; typedef vector VL; typedef vector VE; //static const int INF = 2147483647; //static const long long INf = 9223372000000000000; //static const long long INF = 9223372000000000000/2; static const int INF = 1000010000; static const int NIL = -1; static const int MOD = 1000000007; #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define np next_permutation #define pq priority_queue #define itn int #define scnaf scanf #define reutnr return #define scamf scanf //int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0}; //int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0}; //int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0}; //int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0}; //#define int ll const int NMAX = 114; const int KMAX = 1145; int n,m,k; VE G[NMAX]; int d[KMAX]; int dp[KMAX][NMAX]; //dp[i][j]はi番目に街jを使うときの通り void print(){ for(int i=0;i<=k;i++){ for(int j=0;j