/*
		Keep It Simple!
*/

#include<cstdio>
#include<list>
#include<queue>

#define MaxN 100001
#define inf 1<<30

using namespace std;

int N,M,Dist[MaxN];
bool InQ[MaxN];
list< pair<int,int> > G[MaxN];
list<int> Queue;

void BellMan(int node)
{
		for(int i=2;i<=N;i++) Dist[i] = inf;
		Queue.push_back(1);
		InQ[1] = 1;
		while(Queue.size())
		{
				int nod = Queue.front();
				Queue.pop_front();

				for(list< pair<int,int> >::iterator it = G[nod].begin(); it!=G[nod].end(); it++)
				{
						int r = it->first;
						Dist[it->first] = min(Dist[it->first],Dist[nod] + it->second);
   					if(!InQ[it->first] && (Dist[nod] + it->second) == Dist[it->first])
							{
									Queue.push_back(it->first);
									InQ[it->first] = 1;
							}
				}
		}
}

int main()
{
		freopen("bellmanford.in","r",stdin);
		freopen("bellmanford.out","w",stdout);

		scanf("%d%d",&N,&M);
		int x,y,c;
		for(int i=1;i<=M;i++)
		{
				scanf("%d%d%d",&x,&y,&c);
				G[x].push_back( make_pair(y,c) );
    }

		BellMan(1);

		for(int i=2;i<=N;i++)
				printf("%d ",Dist[i]);
}