#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2010,inf=1e18;
int T,n,m,ans=inf,u,v,w,p,pp,d[N],dis[N][N],vis[N];
struct S{int v,w;bool friend operator <(const S a,const S b){return a.w>b.w;}}Q;
vector<int> g[N];
priority_queue<S> q;
void dij(int s){
	for(int i=1;i<=n;i++)d[i]=1e15;
	d[s]=0,q.push((S){s,0});
	while(!q.empty()){
		Q=q.top();q.pop();
		if(vis[Q.v])continue;
		vis[Q.v]=1;
		for(int y:g[Q.v]){
			w=dis[Q.v][y];
			if((d[Q.v]+w<d[y])&&w)d[y]=d[Q.v]+w,q.push((S){y,d[y]});
		}
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		if(T==1)dis[u][v]=w,g[u].push_back(v);
		else dis[u][v]=dis[v][u]=w,g[u].push_back(v),g[v].push_back(u);
	}
	for(int x=1;x<=n;x++)for(int y=1;y<=n;y++)if(dis[x][y]){
		p=dis[x][y],pp=dis[y][x],dis[x][y]=dis[y][x]=0;
		dij(y);
		ans=min(ans,d[x]+p),dis[x][y]=p,dis[y][x]=pp;
	}
	if(ans>1e14)cout<<"-1\n";
	else cout<<ans<<"\n";
	return 0;
}