#include<iostream>
#include<fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
long viz[250000],d[250000],tata[250000];
long n,m;

struct mat{
    long v[50000];
}b[5000];

void cit()
{
    f>>n>>m;
    int x,y,z;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) b[i].v[j]=0;
                else
                    b[i].v[j]=10000;

    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        b[x].v[y]=z;
    }
}

void dijkstra(int x0)
{
    int mn,ok,k;
    for(int i=1;i<=n;i++)
    {
        d[i]=b[x0].v[i];
        tata[i]=0;
        viz[i]=0;
    }

    viz[x0]=1;
    tata[x0]=0;
    ok=1;
    while(ok==1)
    {
        mn = 1000;
        for(int i=1;i<=n;i++)
            if(viz[i]==0 and mn>d[i])
            {
                mn=d[i];
                k=i;
            }
        if(mn!=1000)
        {
            viz[k]=1;
            for(int i=1;i<=n;i++)
            if (viz[i] == 0 && d[i] > d[k] + b[k].v[i])
            {
                d[i] = d[k] + b[k].v[i];
                    tata[i] = k;
            }
        }
        else ok = 0;
    }
}

int main()
{
    cit();
    dijkstra(1);
    for(int i=1;i<=n;i++)
       if(i!=1)
        g<<d[i]<<" ";
}