#include<bits/stdc++.h>

using namespace std;

#define forn(i,n) for(int i=0; i<(int)(n); i++)
#define forsn(i,s,n) for(int i=(int)(s); i<(int)(n); i++)

int main(){
    int n, m;
    cin>>n>>m;
    const int INF = 2e9;
    vector< vector<int> > matriz(n, vector<int>(n, INF));
    forn(i, m){ // Ingresamos aristas
        int u, v, d;
        cin>>u>>v>>d;
        matriz[u][v]=d;
        matriz[v][u]=d;
    }
    int s=0; // seteamos la ciudad desde la cual queremos empezar
    vector< vector<int> > mejorCamino((1<<n), vector<int>(n, INF));
    mejorCamino[(1<<s)][s]=0;
    forn(i, n){
        if(i!=s){
            mejorCamino[(1<<s)+(1<<i)][i]=matriz[s][i];
        }
    }
    forsn(i, 1, (1<<n)){ // no tiene sentido ver el conjunto vacio
        int subcon=i|(1<<s); // Si o si tengo que incluir a s
        forn(c, n){ // quiero terminar en c
            if( c!=s && (subcon & (1<<c)) ){ // tiene sentido terminar ahi solo si esta en subcon
                int best = INF;
                forn(a, n){ // pruebo que la ciudad a sea la anteultima
                    if( a!=c && (subcon & (1<<a)) ){
                        best=min(best, mejorCamino[subcon-(1<<c)][a] + matriz[a][c]);
                    }
                }
                mejorCamino[subcon][c]=best;
            }
        }
    }
    int ans=INF;
    int ultima;
    forn(i, n){
        if(i!=s){
            int terminandoAca = mejorCamino[(1<<n)-1][i] + matriz[i][s];
            if(ans>terminandoAca){
                ans=terminandoAca;
                ultima=i;
            }
        }
    }
    cout<<"El camino más corto mide "<<ans<<" y termina en la ciudad "<<ultima<<endl;
}