#include <iostream>
#include <stdio.h>
#include <vector>
#include <list>
#include <algorithm>
#define MAXINT 1000000000

using namespace std;
struct edge
{
	int to,cost;
};
typedef vector<int> VEC_OF_I;
typedef list<edge> LIST_OF_E;
typedef vector<LIST_OF_E> VEC_OF_LIST_OF_E;

FILE *fin=fopen("dijkstra.in","r");
FILE *fout=fopen("dijkstra.out","w");

int get_min(VEC_OF_I &Q, VEC_OF_I &dist)
{
	int M=Q.front();
	Q.front()=Q.back();
	Q.pop_back();
	int i=0;
	while(((2*i+1)<Q.size() && dist[Q[i]]>dist[Q[2*i+1]])||((2*i+2)<Q.size() && dist[Q[i]]>dist[Q[2*i+2]]))
	{
		if(dist[Q[i]]>dist[Q[2*i+1]])
		{
			swap(Q[i],Q[2*i+1]);
			i=2*i+1;
		}
		else
		{
			swap(Q[i],Q[2*i+2]);
			i=2*i+2;
		}
	}
	return M;
}

void ins(int x,VEC_OF_I &Q,VEC_OF_I &dist)
{
	Q.push_back(x);
	int i=Q.size()-1;
	while(Q[i]<Q[(i-1)/2])
	{
		swap(Q[i],Q[(i-1)/2]);
		i=(i-1)/2;
	}
}

void dijkstra(int s, int n, int m, VEC_OF_LIST_OF_E &adj_list,VEC_OF_I &dist)
{
	dist[s]=0;
	VEC_OF_I Q;
	Q.push_back(s);
	while(!Q.empty())
	{
		int curr=get_min(Q,dist);
		for(LIST_OF_E::iterator it=adj_list[curr].begin();it!=adj_list[curr].end();it++)
		{
			if((dist[curr]+(*it).cost)<dist[(*it).to])
			{dist[(*it).to]=dist[curr]+(*it).cost;
				ins((*it).to,Q,dist);
			}
		}
	}

}

void show_dist(VEC_OF_I &dist,int n)
{
	for(int i=2;i<=n;i++)
	{
		if(dist[i]<MAXINT)fprintf(fout, "%d ", dist[i]);
		else fprintf(fout, "%d ", 0);
	}
}

int main()
{
	int n,m;
	fscanf(fin,"%d %d",&n,&m);
	VEC_OF_I dist(n+3,MAXINT);
	VEC_OF_LIST_OF_E adj_list(n+3);
	edge tmp;
	int from, to, cost;
	for(int i=1;i<=m;i++)
		{
			fscanf(fin,"%d %d %d",&from,&to,&cost);
			tmp.to=to;
			tmp.cost=cost;
			adj_list[from].push_back(tmp);
		}
	dijkstra(1,n,m,adj_list,dist);
	show_dist(dist,n);


}