#include
#include
#include
using namespace std;
#define MAX 5
#define INF (1<<20)
#define DEBUG if(0)
#define pii pair< int, int >
#define pb(x) push_back(x)
class Node
{
int id:
int p[1][2];
class Node *next[5];
bool operator() (const pii &a, const pii &b)
{
return a.second > b.second;
} ;
priority_queue< pii, vector< pii >, Node > Q;
vector< pii > G[MAX];
int D[MAX];
bool F[MAX];
int main()
{
int i, u, v, w, sz, nodes, edges, starting;
// create graph
cin >> nodes >> edges;
for(i=0; i
{
cin>> u >> v >> w;
G[u].pb(pii(v, w));
G[v].pb(pii(u, w)); // for undirected
}
cin >> starting;
for(i=1; i<=nodes; i++) D[i] = INF;
D[starting] = 0;
Q.push(pii(starting, 0));
while(!Q.empty())
{
u = Q.top().first;
Q.pop();
if(F[u]) continue;
sz = G[u].size();
DEBUG cout<<"visiting from "<< u;
for(i=0; i
{
v = G[u][i].first;
w = G[u][i].second;
if(!F[v] && D[u]+w < D[v])
{
DEBUG cout<< v;
D[v] = D[u] + w;
Q.push(pii(v, D[v]));
}
}
DEBUG cout << "\n";
F[u] = 1;
}
for(i=1; i<=nodes; i++)
cout << "Node"<< i<< "min weight"<< D[i]);
return 0;
}