dikstra

#include<bits/stdc++.h>
using namespace std;
#define f(i,x,y) for (int i = x; i < y; i++)
#define fd(i,x,y) for(int i = x; i>= y; i--)
#define FOR(it,A) for(typeof A.begin() it = A.begin(); it!=A.end(); it++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define vint vector<int>
#define ll long long
#define clr(A,x) memset(A, x, sizeof A)
#define pb push_back
#define pii pair<int,int>
#define fst first
#define snd second
#define ones(x) __builtin_popcount(x)
#define cua(x) (x)*(x)
#define eps (1e-9)
#define oo (1<<30)
#define M 100

vector<pii> Graph[M];
ll dis[M];

bool operator<(pii A, pii B){
	return dis[A.snd] < dis[B.snd];
}

void dijkstra(int s){
	memset(dis,1,sizeof dis);
	dis[s]=0;
	multiset<pii> PQ;
	//priority_queue<pii, vector<pii>, greater<pii> > PQ;
	PQ.insert(pii(0,s));

	//PQ.push(pii(0,s));
	while(!PQ.empty()){
		//pii top=PQ.top(); PQ.pop();
		pii top = *PQ.begin();
		PQ.erase(PQ.begin());
		int d,u;
		d=top.first; u=top.second;
		if(dis[u]==d){
			FOR(it,Graph[u]){
				int v=it->fst;
				int w=it->snd;
				if(dis[u]+w <dis[v]){
					dis[v]=dis[u]+w;
					PQ.insert(pii(dis[v],v));
					//PQ.push(pii(dis[v],v));
				}
			}
		}
	}
}


int main(){
int N;cin>>N;
for(int i=0;i<N;i++){
	int u,v,w;cin>>u>>v>>w;
	Graph[u].pb(pii(v,w));
	Graph[v].pb(pii(u,w));
}

printf("Grafo: \n");
for(int i=0;i<N;i++){
	printf("Nodo %d:\t",i);
	FOR(it,Graph[i]){
		printf("%d (%d)\t",it->fst,it->snd);
	}
	cout<<endl;
}

dijkstra(0);
printf("distancias: \t\n");
for(int i=0;i<5;i++) cout<<dis[i]<<endl;

return 0;
}