#include<stdio.h>
#include<queue>
#include<vector>
#define INF 1000000000
using namespace std;
vector<int> G[50005],C[50005];
int n,d[50005];
struct Nod
{
	int u,cost;
	Nod() {u=cost=0;}
	Nod(int a,int b) {u=a;cost=b;}
	inline bool operator<(const Nod &other) const
	{
		return cost<other.cost;
	}
};
void dijk()
{
	priority_queue<Nod> q;
	for(int i=2;i<=n;i++)
		d[i]=INF;
	q.push(Nod(1,0));
	while(!q.empty())
	{
		int val=q.top().cost,x=q.top().u;
        	q.pop();
        	for(int i=0;i<(int)G[x].size(); i++)
         	if(d[G[x][i]]>val+C[x][i])
            		d[G[x][i]]=val+C[x][i],
			q.push(Nod(G[x][i],d[G[x][i]]));
    }
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int m,x,y,c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		G[x].push_back(y);
		C[x].push_back(c);
	}
	dijk();
	for(int i=2;i<=n;i++)
		if(d[i]==INF)
			printf("0 ");
		else printf("%d ",d[i]);
	return 0;
}