#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4002,inf=1e18;
int t,n,m,u[N],v[N],w[N],f[N];
bool vis[N],pa[N];
vector<int> x[N],y[N],z[N];
struct node{
	int x,id,ba;
	friend bool operator <(const node &x,const node &y){
		if(x.x!=y.x) return x.x>y.x;
		else return x.id>y.id;
	}
};
priority_queue<node> p;
void dij(int s){
    for(int i=1;i<=n;i++) vis[i]=0,f[i]=inf;
    for(int i=1;i<=m;i++)pa[i]=0;
    p.push((node){0,s});
    f[s]=0;
    while(!p.empty()){
        int op=p.top().id,sum=p.top().ba;
        p.pop();
        if(vis[op])continue;
        vis[op]=1;
        pa[sum]=1;
        for(int i=0;i<x[op].size();i++){
            if(y[op][i]+f[op]<f[x[op][i]]){
                f[x[op][i]]=y[op][i]+f[op];
                p.push((node){f[x[op][i]],x[op][i],z[op][i]});
            }
        }
    }
    return;
}
signed main(){
    cin>>t>>n>>m;
    if(t==0){
        for(int i=1;i<=m;i++){
            cin>>u[i]>>v[i]>>w[i];
            x[u[i]].push_back(v[i]);
            x[v[i]].push_back(u[i]);
            y[u[i]].push_back(w[i]);
            y[v[i]].push_back(w[i]);
            z[u[i]].push_back(i);
            z[v[i]].push_back(i);
        }
        int ans=inf;
        for(int i=1;i<=n;i++){
            dij(i);
            for(int j=1;j<=m;j++){
                if(pa[j]==0){
                    ans=min(ans,f[u[j]]+f[v[j]]+w[j]);
                }
            }
        }
        if(ans==inf) ans=-1;
        cout<<ans<<endl;
    }
    else {
        for(int i=1;i<=m;i++){
            cin>>u[i]>>v[i]>>w[i];
            x[u[i]].push_back(v[i]);
            y[u[i]].push_back(w[i]);
            z[u[i]].push_back(i);
        }
        int ans=inf;
        for(int i=1;i<=n;i++){
            dij(i);
            for(int j=1;j<=m;j++){
                if(v[j]==i){
                    ans=min(ans,f[u[j]]+w[j]);
                }
            }
        }
        if(ans==inf) ans=-1;
        cout<<ans<<endl;
    }
    return 0;
}
/*
*/