#include #include #include #include #include #include using namespace std; #define int long long #define rep(i,n) for(int i = 0; i < (n); i++) #define endl "\n" const long long INF = (long long)1e18; const long long MOD = (long long)1e9 + 7; string yn(bool f){return f?"Yes":"No";} string YN(bool f){return f?"YES":"NO";} #define MAX 20 signed main(){ cin.tie(0); ios::sync_with_stdio(false); cout<>N>>M; for(int i = 0; i < M; i++){ cin>>a>>b>>c; a--, b--; cost[a][b] = c; cost[b][a] = c; } for(int i = 1; i < (1<