#include<cstdio>
#include<vector>
using namespace std;
const int N=50001,I=1<<30;
int n,m,i,x,y,z,d[N],h[N],p[N],k,l,j;
vector<int> a[N],b[N];
void U(int i)
{
	for(;i>1&&d[h[i>>1]]>d[h[i]];p[h[i]]=i,p[h[i>>1]]=i>>1,swap(h[i>>1],h[i]),i>>=1);
}
int main()
{
	freopen("dijkstra.in","r",stdin),freopen("dijkstra.out","w",stdout),scanf("%d%d",&n,&m);
    while(m--)
        scanf("%d%d%d",&x,&y,&z),a[x].push_back(y),b[x].push_back(z);
    for(i=2;i<=n;i++)
        d[i]=I,p[i]=-1;
    for(p[1]=h[++k]=1;k;)
    {
        for(l=h[1],h[1]=h[k--],p[h[1]]=i=1;i<=k;i=j)
		{
			j=i;
			if((i<<1)>k)
				break;
			j=i<<1;
			if(j<k&&d[h[1+j]]<d[h[j]])
				j++;
			if(d[h[i]]<=d[h[j]])
				break;
			swap(h[i],h[j]),p[h[i]]=i,p[h[j]]=j;
		}
		for(j=a[l].size(),i=0;i<j;i++)
            if(d[a[l][i]]>d[l]+b[l][i])
            {
                d[a[l][i]]=d[l]+b[l][i];
                if(p[a[l][i]]!=-1)
                    U(p[a[l][i]]);
                else
                    h[++k]=a[l][i],p[h[k]]=k,U(k);
            }
	}
    for(i=2;i<=n;i++)
        printf("%d ",d[i]==I?0:d[i]);
}