#include<cstdio>
#include<set>
using namespace std;
const int N=50001,M=250001,I=1<<30;
set<pair<int,int>> c;
int n,m,d[N],i,j,a[M],b[M],e[M],*s[N],*v[N],w[N];
int main()
{
	freopen("dijkstra.in","r",stdin),freopen("dijkstra.out","w",stdout),scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
    	scanf("%d%d%d",a+i,b+i,e+i),w[a[i]]++;
	for(i=1;i<=n;d[i]=N,w[i++]=0)
		s[i]=new int[w[i]],v[i]=new int[w[i]];
	for(i=1;i<=m;i++)
    	s[a[i]][w[a[i]]]=b[i],v[a[i]][w[a[i]]++]=e[i];
	for(d[1]=0,c.insert({0,1});!c.empty();)
		for(i=c.begin()->second,c.erase(c.begin()),j=0;j<w[i];j++)
            if(d[i]+v[i][j]<d[s[i][j]])
                d[s[i][j]]=d[i]+v[i][j],c.insert({d[s[i][j]],s[i][j]});
	for(i=2;i<=n;i++)
        printf("%d ",d[i]%N);
}