#include<fstream>
#include<iostream>
#include<vector>
#define lmare 132000
#define lmic 51000
#define infinit 300000
using namespace std;

struct muchie{
	int inf;
	int cost;
}y;
vector<muchie>v[lmic];
int D[lmic];
int parcurs[lmic];
int h[lmare];

void creareheap(int nod, int st, int dr){
	if(st==dr){
		cout<<"b";
		if(st==1)h[nod]=0;
		else h[nod]=infinit;
		D[st]=infinit;
	}
	else{
		int mij=(st+dr)/2;
		creareheap(2*nod,st,mij);
		creareheap(2*nod+1,mij+1,dr);
		if(h[2*nod]<h[2*nod+1])h[nod]=h[2*nod];
        else h[nod]=h[2*nod+1];
	}
}

void actualizareheap(int nod,int st,int dr,int cost,int p){
	if(st==dr)h[nod]=cost;
	else{cout<<"D";
		int mij=(st+dr)/2;
		if(p<=mij)actualizareheap(2*nod,st,mij,cost,p);
		else actualizareheap(2*nod+1,mij+1,dr,cost,p);
		if(h[2*nod]<h[2*nod+1])h[nod]=h[2*nod];
        else h[nod]=h[2*nod+1];
   }
}

void parcurg(int a,int n){
	int i;
	for(i=0;i<v[a].size();i++)
		if((parcurs[v[a][i].inf]==0)&&(D[a]+v[a][i].cost<D[v[a][i].inf])){
            D[v[a][i].inf]=D[a]+v[a][i].cost;
			actualizareheap(1,1,n,D[v[a][i].inf],v[a][i].inf);}
	parcurs[a]=1;
}

int minim(int nod,int st,int dr){
	if(st==dr)return st;
	else{cout<<"c";
		int mij=(st+dr)/2;
		if(h[2*nod]<h[2*nod+1])return minim(2*nod,st,mij);
		return minim(2*nod+1,mij+1,dr);
	}
}

void afisare(int n){
	int i;
	ofstream g("dijkstra.out");
	for(i=2;i<=n;i++)
		if(D[i]!=infinit)g<<D[i]<<" ";
	else g<<"0"<<" ";
}
main(){
	int n,m,a,i;
	ifstream f("dijkstra.in");
	f>>n>>m;
	for(i=1;i<=m;i++){
		f>>a>>y.inf>>y.cost;
		v[a].push_back(y);}
	creareheap(1,1,n);
	while(h[1]!=infinit){
		a=minim(1,1,n);
		D[a]=h[1];
		parcurg(a,n);
		actualizareheap(1,1,n,infinit,a);
	}
	afisare(n);
}