#include <cstdio>
using namespace std;
int m,min1,b[50001],d[50001],a[10001][10001];
unsigned short n,i,j,k,p;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%hu %d\n",&n,&m);
    while(m)
    {
        scanf("%hu %hu %hu\n",&i,&j,&k);
        if(!k)
            k--;
        a[i][j]=k;
        m--;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            if(!a[i][j] && i!=j)
                a[i][j]=2000000000;
            else
                if(a[i][j]==-1)
                    a[i][j]++;
            if(i==1)
                d[j]=a[i][j];
        }
    p=1;
    while(p<n)
    {
        p++;
        min1=1000000001;
        for(i=2;i<=n;i++)
            if(d[i]<min1 && !b[i])
            {
                min1=d[i];
                k=i;
            }
        b[k]=1;
        for(i=2;i<=n;i++)
            if(min1+a[k][i]<d[i] && !b[i])
                d[i]=min1+a[k][i];
    }
    for(i=2;i<=n;i++)
        printf("%d ",d[i]);
    printf("\n");
    return 0;
}