#define inf 1000001
#define M 50005
#include <fstream>
using namespace std;
ifstream g("dijkstra.in");
ofstream o("dijkstra.out");
int n,m,coada[5*M],d[M],start,n1,n2,h;

struct nod{

int cost;
int x;
nod *urm;

};
nod *L[M];

void adauga(int i, int j, int h)
{
    nod *p;
    p=new nod;
    p->x=j;
    p->cost=h;
    p->urm=L[i];
    L[i]=p;

}

void bellman(int nod_pornire)
{
    int pr,ul;
    nod *p;
    pr=ul=1;
    coada[1]=nod_pornire;
    for(int i=1;i<=n;i++)
        d[i]=inf;
    d[nod_pornire]=0;

    while(pr<=ul)
    {
        p=L[coada[pr]];
        pr++;
        while(p)
        {
            if(d[p->x]>d[coada[pr-1]]+p->cost)
            {
                d[p->x]=d[coada[pr-1]]+p->cost;
                coada[++ul]=p->x;
            }
            p=p->urm;
        }
    }


}


int main()
{
    g>>n>>m ;

    for(int i=1;i<=m;i++)
    {
        g>>n1>>n2>>h;
        adauga(n1,n2,h);
    }
    bellman(1);

    for(int i=1+1;i<=n;i++)
        if(d[i]==inf)
        o<<0;
        else
        o<<d[i]<<" ";
    return 0;
}