#include <bits/stdc++.h>
#define lint __int128
#define int long long
#define Il inline
#define fi first
#define se second
#define vec vector
#define pb push_back
#define IT ::iterator
#define p_q priority_queue

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const int N=2e3,Inf=1e18;
const db eps=1e-9,pi=acos(-1.0);

mt19937 rnd(time(0));
Il int rint(int l,int r){return rnd()%(r-l+1)+l;}

int n,m,ex[N+5],ey[N+5],ew[N+5],tmp,dis[N+5],ans=Inf;
vec<pii>v[N+5];
bool vis[N+5];
struct Nodj{int ds,ps;Il bool operator <(const Nodj &s)const{return ds>s.ds;}};
p_q<Nodj>dj;

Il void dijk(int id,int s){
    dj.push({0,s});for(int i=1;i<=n;i++)dis[i]=(i^s?Inf:0),vis[i]=0;
    while(!dj.empty()){
        int fq=dj.top().ps;dj.pop();if(vis[fq])continue;
        vis[fq]=1;for(pii i:v[fq])if((i.se^id)&&dis[i.fi]>dis[fq]+ew[i.se])dj.push({dis[i.fi]=dis[fq]+ew[i.se],i.fi});
    }
    return;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>tmp>>n>>m;for(int i=1;i<=m;i++){cin>>ex[i]>>ey[i]>>ew[i];v[ex[i]].pb({ey[i],i});if(!tmp)v[ey[i]].pb({ex[i],i});}
    for(int i=1;i<=m;i++)dijk(i,ey[i]),ans=min(ans,dis[ex[i]]+ew[i]);
    cout<<(ans^Inf?ans:-1);
    return 0;
}