#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,S,T,tot,mk[50010];
ll dp[50010];
struct node {
    int idx,val,nxt,hd;
}e[10010];
void add (int u,int v,int w) {
    e[++tot].idx=v;
    e[tot].val=w;
    e[tot].nxt=e[u].hd;
    e[u].hd=tot;
}
int dijkstra () {
    memset(dp,0x3f,sizeof(dp));
    dp[S]=0;
    priority_queue<int>q;
    q.push(S);
    mk[S]=1;
    while (q.size()) {
        int t=q.top();
        q.pop();
        for (int i=e[t].hd;i;i=e[i].nxt) {
            int y=e[i].idx;
            if (dp[y]>dp[t]+e[i].val) {
                dp[y]=dp[t]+e[i].val;
                mk[y]=1;
                q.push(y);
            }
        }
    }
    return dp[T];
}
int main () {
    freopen("move.in","r",stdin);
    freopen("move.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    //memset(dp,1e3+10,sizeof(dp));
    cin >> n >> m >> k;
    cin >> S >> T;
    for (int i=1;i<=m;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
    }
    if (k==0) {
         cout << dijkstra() <<endl;
    }else if (k==1) {
        int ans=1e9;
        for (int i=1;i<=tot/2;i++) {
            memset(mk,0,sizeof(mk));
            int k=e[i*2].val;
            e[i*2].val=0;
            e[i*2-1].val=0;
            int res=dijkstra();
            if (res<ans) ans=res;
            e[i*2].val=k;
            e[i*2-1].val=k;
        }
        cout << ans <<endl;
    }else {
        cout << 111 <<endl;
    }
    return 0;
}