#include <iostream>
#include <fstream>

#define dim 50001

using namespace std;

const int inf = 2000000000; ///infinit

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct graf
{
    int nod,len;
    graf* next;
}*a[dim];

int n,m,H[dim],d[dim],poz[dim];

inline int father(int nod)
{
    return nod / 2;
}

inline int left_son(int nod)
{
    return nod * 2;
}

inline int right_son(int nod)
{
    return nod * 2 + 1;
}

inline int mini_heap()
{
    return H[1];
}

void sift(int K)
{
    int son;
    do
    {
        son = 0;
        // Alege un fiu mai mare ca tatal.
        if (left_son(K) <= n)
        {
            son = left_son(K);
            if (right_son(K) <= n && d[H[right_son(K)]] < d[H[left_son(K)]])
            {
                son = right_son(K);
            }
            if (d[H[son]] >= d[H[K]])
            {
                son = 0;
            }
        }

        if (son)
        {
            swap(H[K], H[son]);
            poz[H[K]]=son;
            poz[H[son]]=K;
            K = son;
        }
    }
    while (son);
}

void percolate(int K)
{
    int key = H[K];
    //int aux = poz[H[K]];

    while ((K > 1) && (d[key] < d[H[father(K)]]))
    {
        H[K] = H[father(K)];
        poz[H[father(K)]]=K;
        K = father(K);
    }

    H[K] = key;
    poz[H[K]] = K;
}

void cut(int K)
{
    H[K] = H[n];
    poz[H[K]] = K;
    --n;

    if ((K > 1) && (d[H[K]] > d[H[father(K)]]))
    {
        percolate(K);
    }
    else
    {
        sift(K);
    }
}

void build_heap()
{
    for (int i = n / 2; i > 0; --i)
    {
        sift(i);
    }
}

void afisare(int a[])
{
    for (int i=1; i<=n; i++)
        cout<<a[i]<<' ';
    cout<<'\n';
}

void afisare(bool a[])
{
    for (int i=1; i<=n; i++)
        cout<<a[i]<<' ';
    cout<<'\n';
}

int main()
{
    fin>>n>>m;
    for (int i=0; i<m; i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        graf* nou=new graf;
        nou->nod=y;
        nou->len=cost;
        nou->next=a[x];
        a[x]=nou;
    }
    d[1]=0;
    H[1]=1;
    poz[1]=1;
    for (int i=2; i<=n; i++)
        d[i]=inf,H[i]=i,poz[i]=i;
    graf* i=a[1];
    while(i!=NULL)
    {
        d[i->nod]=i->len;
        i=i->next;
    }
    build_heap();
    int auxn=n;
    while (n)
    {
        int nodcurent=mini_heap();
        cut(1);
        graf* j=a[nodcurent];
        while (j!=NULL)
        {
            if (d[nodcurent]+j->len<d[j->nod])
            {
                d[j->nod]=d[nodcurent]+j->len;
                percolate(poz[j->nod]);
            }
            j=j->next;
        }
    }
    for (int i=2; i<=auxn; i++)
    {
        if (d[i]==inf)
            d[i]=0;
        fout<<d[i]<<' ';
    }
    //afisare(d);
    //afisare(s);
    //afisare(t);
    return 0;
}