#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template<class T> bool chmin(T& a,T b){if(a>b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b){if(a<b) {a = b; return true;} return false;}
#define rep(i,n) for(int i=0;i<(n);i++)
#define drep(i,n) for(int i=(n)-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define debug(x)  cerr << #x << " = " << (x) << endl;

using P = pair<ll,int>;
constexpr ll inf = 1e18;


void dijkstra(int s,vvec<P>& g,vec<ll>& dist, pair<int,int> forbid = {-1,-1}){
    dist[s] = 0;
    priority_queue<P,vec<P>,greater<P>> Q;
    Q.push({0,s});
    while(!Q.empty()){
        auto [d,cur] = Q.top(); Q.pop();
        if(dist[cur]<d) continue;
        for(auto& [c,to]:g[cur]){
            pair<int,int> p = {to,cur};
            if(p.first>p.second) swap(p.first,p.second);
            if(forbid!=p){
                if(chmin(dist[to],dist[cur]+c)){
                    Q.push({dist[to],to});
                }
            }
        }
    }
}

void solve0(){
    int N,M;
    cin >> N >> M;
    vvec<P> g(N);
    rep(i,M){
        int a,b,c;
        cin >> a >> b >> c;
        a--,b--;
        g[a].emplace_back(c,b);
        g[b].emplace_back(c,a);
    }
    ll ans = inf;
    rep(i,N){
        for(auto& [c,to]:g[i]){
            vec<ll> dist(N,inf);
            dijkstra(i,g,dist,minmax({i,to}));
            chmin(ans,dist[to]+c);
        }
    }
    cout << (ans!=inf? ans:-1) << "\n";
}

void solve1(){
    int N,M;
    cin >> N >> M;
    vvec<P> g(N);
    rep(i,M){
        int a,b,c;
        cin >> a >> b >> c;
        a--,b--;
        g[a].emplace_back(c,b);
    }
    ll ans = inf;
    rep(i,N){
        vec<ll> dist(N,inf);
        dijkstra(i,g,dist);
        rep(j,N){
            for(auto& [c,to]:g[j]) if(to==i) chmin(ans,dist[j]+c); 
        }
    }
    cout << (ans!=inf? ans:-1) << "\n";
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    if(T==0) solve0();
    else solve1();
}