#include <bits/stdc++.h>

#define MAX             100005
#define INF             INT_MAX
#define pii             pair<int,int>

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

using namespace std;

int dijkstra(int src, int dst, vector<vector<pii>> &adj)
{
    vector<int> dis(MAX, INF);
    //dis[100005]={INT_MAX} ; why doesn't work(gives wrong answer) I don't know!
    dis[src]=0;

    priority_queue<pii, vector<pii>, greater<pii> >pq;
    pq.push({0, src}); // Insert source in priority queue and initialize its distance as 0.

    while(!pq.empty())
    {
        int u=pq.top().second;
        int cost=pq.top().first;
        pq.pop();

        //Optimization in the priority queue:
        /*
        Ideally, for updating the priority queue, we must delete the old value and reinsert with the
        new cost value. But, as we know that the updated cost value is always lesser than the old
        value and would be popped from the queue and visited before the old value,
        we could save time and avoid removing the old value from the queue.
        */
        if(dis[u]<cost) continue;

        for(int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first;
            cost=adj[u][i].second;

            if(dis[v]>dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
                pq.push({dis[v], v});
            }
        }
    }
    return dis[dst];
}

//unordered_map<string,int> mp; //for string input

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int node, edge;
    cout<<"Enter number of nodes: \n";
    cin>>node;
    cout<<"Enter number of edges: \n";
    cin>>edge;
    //int c=1;

    cout<<"Enter the edges and their corresponding cost (node node cost):"<<endl;

    vector<vector<pair<int,int> > > adj(MAX);
    //vector<pair<int,int>> adj[node]; //can also be written like this

    for(int i=0; i<edge; i++)
    {
        int from,to,cost;
        //string frm,to;
        cin>>from>>to>>cost;

//        if(mp[frm]==0)
//        {
//            mp[frm]=c;
//            c++;
//        }
//        if(mp[to]==0)
//        {
//            mp[to]=c;
//            c++;
//        }

        adj[from].push_back({to, cost});
        adj[to].push_back({from, cost}); //If undirected graph
//        g[mp[frm]].push_back(mp[to]);
//        g[mp[to]].push_back(mp[frm]); //If undirected graph
    }

    int src,dst;
    //string src,dst;

    cin>>src>>dst;

    int min_distace=dijkstra(src, dst, adj);
    //int min_distace=dijkstra(mp[src],mp[dst], adj);
    if(min_distace==INF) cout<<"No path"<<endl;
    else
    {
        cout<<"Shortest distance with min cost: "<<min_distace<<endl;
    }
    return 0;
}