//Bellman - Ford

#include <cstdio>
#define max 999999999

using namespace std;

struct muchie{int x,y,cost;} a[250001];
int d[5001],ok,n,m;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].cost);
        if(a[i].x==1)
            d[a[i].y]=a[i].cost;
    }
    for(int i=1;i<=n;i++)
        if(d[i]==0)
            d[i]=max;
    while(ok==0)
    {
        ok=1;
        for(int i=1;i<=m;i++)
            if(d[a[i].y]>d[a[i].x]+a[i].cost)
            {
                d[a[i].y]=d[a[i].x]+a[i].cost;
                ok=0;
            }
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==max)
            printf("0 ");
        else
            printf("%d ",d[i]);
    }
    return 0;
}