#include<bits/stdc++.h>
using namespace std;

const int NMax = 50001;
const int inf = 1 << 30; // 1 urmat de 30 zero

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

struct Graf
{
    int nod, cost;
    Graf* next;
};

int n, m;
Graf *a[NMax];
int d[NMax], h[NMax], poz[NMax], k;

void add(int where, int what, int cost)
{
    Graf *q = (Graf*)malloc(sizeof(Graf));
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}

void read()
{
    in >> n >> m;
    int x, y, z;
    for(int i = 1; i <= m; ++i)
    {
        in >> x >> y >> z;
        add(x, y, z);
    }
}

void swapp(int x, int y)
{
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;
}

void upheap(int what)
{
    int tata;
    while( what > 1)
    {
        tata = what >> 1;
        if(d[h[tata]] > d[ h[what] ])
        {
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;

            swapp(tata, what);
            what = tata;
        }else what = 1;
    }
}

void downheap(int what)
{
    int f;
    while( what <= k )
    {
        f = what;
        if( (what<<1) <= k )
        {
            f = what << 1;
            if( f+1 <= k )
                if(d[ h[f+1] ] < d[ h[f] ])
                    ++f;
        }else return;


    if(d[ h[what] ] > d[ h[f] ])
    {
        poz[h[what]] = f;
        poz[h[f]] = what;
        swapp(what, f);
        what = f;
    }
    else return;
    }
}

void dijkstra_heap()
{
    for( int i = 2; i <= n; ++ i)
    {
        d[i] = inf; // distanta initiala pentru fiecare nod de la sursa este infinit
        poz[i] = -1; // si pozitia lor e -1;
    }
    poz[1] = 1; // pozitia nodului sursa este 1;
    h[++k] = 1;
    while( k )
    {
        int minn = h[1];
        swapp(1, k);
        poz[ h[1] ] = 1;
        -- k;

        downheap(1);
        Graf *q = a[ minn ];
        while(q)
        {
            if(d[q->nod] > d[minn] + q->cost)
            {
                d[q->nod] = d[minn] + q->cost;
                if(poz[q->nod] != -1)
                {
                    upheap(poz[q->nod]);
                }
                else{
                    h[++k] = q->nod;
                    poz[ h[k] ] = k;
                    upheap(k);
                }
            }
            q = q->next;
        }
    }
}

int main()
{
    read();
    dijkstra_heap();
    for(int i = 2; i <= n; ++i)
    {
        if(d[i] == inf)
            out<<0;
        else
            out<<d[i]<<" ";
    }
    return 0;
}