#include <bits/stdc++.h>

using namespace std;
int a[100][100],i,j,p,min1,d[100],x,y,z,v[100],n,m;
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",&x,&y,&z);
        a[x][y]=z;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(a[i][j]==0) a[i][j]=99999999;
    for(i=1;i<=n;i++)
        d[i]=a[1][i];
    v[1]=1;
    for(i=1;i<n;i++)
    {
        min1=9999999;
        p=0;
        for(j=1;j<=n;j++)
            if(!v[j]&&d[j]<min1&&d[j])
        {
            min1=d[j];
            p=j;
        }
        if(p) v[p]=1;
        else
            break;
        for(j=1;j<=n;j++)
            if(d[p]+a[p][j]<d[j])
            d[j]=d[p]+a[p][j];
    }
    for(i=2;i<=n;i++)
        printf("%d ",d[i]);

    return 0;
}