#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>

using namespace std;

vector <int> graf[100];
vector <int> utez[100];
int razdalja[100];

int main(){
	int v,e;
	scanf("%d%d",&v,&e);
	for(int i=0;i<e;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		graf[a].push_back(b);
		utez[a].push_back(c);
		graf[b].push_back(a);
		utez[b].push_back(c);
	}
	for(int i=0;i<v;i++)razdalja[i]=-1;
	priority_queue<pair<int,int> > vrsta;
	vrsta.push(make_pair(0,0));
	while(!vrsta.empty()){
		pair<int,int> trenutno = vrsta.top();
		vrsta.pop();
		int vozl = trenutno.second;
		int teza = -trenutno.first;
		if(razdalja[vozl]!=-1)continue;
		razdalja[vozl]=teza;
		for(int i=0;i<graf[vozl].size();i++){
			int sosed = graf[vozl][i];
			if(razdalja[sosed]!=-1)continue;
			vrsta.push(make_pair(-teza-utez[vozl][i],sosed));
		}
	}
	for(int i=0;i<v;i++)printf("Razdalja do %d: %d\n",i,razdalja[i]);
	return 0;
}