Traveling Salesman Problem

/**------------------------
    Author : NikolaP
    Compiler : C++
-------------------------*/

//{         Setup

    #include <bits/stdc++.h>
    using namespace std;

    typedef long long int ll;
    typedef long double ld;
    typedef vector<int> vi;

    const int inf = INT_MAX;
    const bool debug = 0;

//}

struct TSP{
    int n;
    vector<vi> graph;
    vector<vi> dp;

    TSP(int _n, int m){
        n = _n;
        graph.assign(n,vi(n,inf));
        dp.assign(n,vi((1 << n) - 1, inf));

        while(m--){
            int from,to,cost;
            cin >> from >> to >> cost;
            graph[from][to] = cost;
            graph[to][from] = cost;
        }
    }

    int tsp(int position, int visited, int start){
        if(visited == (1 << n) - 1) return graph[position][start];

        if(dp[position][visited] != inf) return dp[position][visited];

        for(int i = 0; i < n; ++i){
            if(i == position or (visited & (1 << i))) continue;

            int distance = graph[position][i] + tsp(i, visited | (1 << i), start);
            dp[position][visited] = min(dp[position][visited] , distance);
        }

        return dp[position][visited];
    }

    int Solution(){
        int ans = inf;

        for(int i = 0; i < n; ++i){
            ans = min(ans, tsp(i, 1 << i, i));
        }

        return ans;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(8);
    //cout << fixed;

    int n,m;
    cin >> n >> m;
    TSP idk = TSP(n,m);
    cout << idk.Solution();
    return 0;
}