#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct aa
{
    int b;
    int c;
    bool operator<(const aa &b)const
    {
    	return c>b.c;
    }
};
vector <aa> vec[50002];
priority_queue <aa> heap;
priority_queue <int> test;
int dist[50002],mark[50002],n,m;
void dijkstra(int x)
{
		int i,l,node,cost,son,costs;
		for(i=1;i<=n;i++)
			dist[i]=2000000000;
		dist[x]=1;
		heap.push({x,0});
		while(!heap.empty())
		{
			cost=heap.top().c;
			node=heap.top().b;
			heap.pop();
			l=vec[node].size();
			if(cost<=dist[node])
			for(i=0;i<l;i++)
			{
				son=vec[node][i].b;
				costs=vec[node][i].c;
				if(dist[son]>cost+costs)
					{dist[son]=cost+costs;
					heap.push({son,dist[son]});}
			}
		}
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
		int i,a,b,c;
		scanf("%d%d",&n,&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			vec[a].push_back({b,c});
		}
		dijkstra(1);
		for(i=2;i<=n;i++)
			if(dist[i]!=2000000000)
			printf("%d ",dist[i]);
			else printf("0 ");

    return 0;
}