#include<map>
#include<set>
#include<vector>
#include<string>
#include<algorithm>

#define MAXN 50000
#define MAX	1000000000
#define pb push_back
#define mkp make_pair


using namespace std;


vector< pair<int,int> >e[MAXN];

int n;
int m;

int val[MAXN][1];
vector<int> nr;




void dij( int tag)
{
	int v[MAXN];
	set< pair<int,int> > next;
	
	for(int i=0;i<n;i++)
		v[i] = val[i][tag];

	
	for(int i=0;i<n;i++)
		next.insert( mkp(val[i][tag],i) );
		
	while(!next.empty())
	{
		int j = next.begin()->second;
		next.erase(next.begin());
		for(int k=0;k<e[j].size();k++)
		{
			int vec = e[j][k].first;
			int cost = e[j][k].second;
			
			if( v[j] + cost < v[ vec ] )
			{
				next.erase(mkp(v[vec ],vec) ); 
				v[ vec] = v[j] + cost;
				next.insert(mkp(v[ vec ],vec) );
			}
		}
	}
	
	for(int i=0;i<n;i++)
		val[i][tag] = v[i];
	
}



int main()
{
	freopen ("dijkstra.in", "r",stdin);
	freopen ("dijkstra.out", "w",stdout);
	
	scanf("%d",&n);
	scanf("%d",&m);
	
	for(int i=0;i<m;i++)
	{	
		int t1,t2,c;
		scanf("%d",&t1);
		scanf("%d",&t2);
		scanf("%d",&c);
		e[t1-1].pb(mkp(t2-1,c));
	}
		
	val[0][0] = 0;
	for(int i=1;i<n;i++)
		val[i][0] =MAX;
	dij(0);
	
	for(int i=1;i<n;i++)
		printf("%d ",(int)val[i][0]);	
	
	return 0;
}