#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
const int INF=1e9+10;
int T,n,m,cnt,ans=INF;
int head[N],nxt[N],to[N],val[N],dis[N],vis[N],fa[N];
struct node{
	int u,v,w;
}a[N];
inline void add(int u,int v,int w){nxt[++cnt]=head[u];head[u]=cnt;to[cnt]=v;val[cnt]=w;return;}
inline void dij(int s){
	dis[s]=0;
	priority_queue<pair<int,int> > q;
	q.push({-dis[s],s});
	while(q.size()!=0){
		pair<int,int> h=q.top();q.pop();
		int x=h.second;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=nxt[i]){
			int y=to[i],w=val[i];
			if(dis[y]>dis[x]+w){
				dis[y]=dis[x]+w;fa[y]=x;
				q.push({-dis[y],y});
			}
		}
	}
}
signed main(){
	cin>>T>>n>>m;
	if(T==0){
		for(int i=1,u,v,w;i<=m;i++){
			cin>>u>>v>>w;
			a[i].u=u;a[i].v=v;a[i].w=w;
			add(u,v,w);
			add(v,u,w);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) dis[j]=INF,vis[j]=0,fa[j]=0;
			dij(i);
			for(int j=1;j<=m;j++){
				int u=a[j].u,v=a[j].v,w=a[j].w;
				if(v==i||u==i) continue;
				if(fa[u]==v||fa[v]==u) continue;
				ans=min(ans,dis[u]+dis[v]+w);
			}
		}
		cout<<ans<<"\n";
	}
	if(T==1){
		for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,add(u,v,w);
		cout<<"A\n";
	}
	return 0;
}