#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;
	}
} a[50005];
int k;
inline int f(int x)
{
	return x+(int)(x<k && a[x+1].cost>a[x].cost);
}
void push(Nod p)
{
	int T,C;
	a[++k]=p;
	for(C=k,T=C/2;T>=1 && a[T].cost>a[C].cost;a[C]=a[T],C=T,T>>=1);
	a[C]=p;
}
void pop_top()
{
	int T,C;Nod aux;
	a[1]=a[k];k--;
	for(T=1,aux=a[1],C=f(2);C<=k && aux.cost<a[C].cost;a[C]=a[T],T=C,C=f(2*T));
	a[T]=aux;
}
void dijk()
{
	for(int i=2;i<=n;i++)
		d[i]=INF;
	a[++k]=Nod(1,0);
	while(k)
	{
		int val=a[1].cost,x=a[1].u;
        	pop_top();
        	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],
			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;
}