#include <cstdio>
#include <vector>
#include <algorithm>
#define min(x,y) (x<y?x:y)
#define tata(x) ((x-1)/2)
#define st(x) (2*x+1)
#define dr(x) (2*x+2)

using namespace std;

struct Muchie
{
    int catre, cost;
};

struct Nod
{
    vector<Muchie> v;
} v[50000];

int h[50000], lh = 0;
int ph[50000];
int cf[50000] = {0};
//bool viz[50000] = {0};

bool cmp(const int& a, const int& b)
{
    return cf[a] > cf[b];
}

void calib(int a)
{
    while(a != 0 && cf[h[a]] < cf[h[tata(a)]])
    {
        swap(h[a], h[tata(a)]);
        ph[h[a]] = tata(a);
        ph[h[tata(a)]] = a;
        a = tata(a);
    }
}

void pop()
{
    int a = 0;
    h[0] = h[lh - 1];
    ph[h[0]] = 0;
    while(true)
    {
        if(st(a) < lh && cf[h[st(a)]] < cf[h[a]] && (dr(a) >= lh || cf[h[dr(a)]] > cf[h[st(a)]]))
        {
            swap(h[a], h[st(a)]);
            ph[h[a]] = st(a);
            ph[h[st(a)]] = a;
            a = st(a);
        }
        else if(dr(a) < lh && cf[h[dr(a)]] < cf[h[a]])
        {
            swap(h[a], h[dr(a)]);
            ph[h[a]] = dr(a);
            ph[h[dr(a)]] = a;
            a = dr(a);
        }
        else break;
    }
    lh--;
}

int main()
{
    int n, m, i, a, b, c, j;
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d", &n, &m);
    cf[0] = 0;
    //viz[0] = true;
    for(i = 1; i < n; i++)
    {
        cf[i] = -1;
    }
    for(i = 0; i < m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        if(b == 1)
            continue;
        Muchie m;
        m.catre = b - 1;
        m.cost = c;
        v[a - 1].v.push_back(m);
    }
    //h.reserve(v[0].v.size());
    for(i = 0; i < v[0].v.size(); i++)
    {
        //h.push_back(v[0].v[i].catre);
        h[lh++] = v[0].v[i].catre;
        ph[v[0].v[i].catre] = i;
        cf[v[0].v[i].catre] = v[0].v[i].cost;
        calib(i);
    }
    //make_heap(h.begin(), h.end(), cmp);
    while(lh)
    {
        a = h[0];
        pop();
        //if(viz[a])
        //    continue;
        //viz[a] = true;
        for(j = 0; j < v[a].v.size(); j++)
        {
            if(cf[v[a].v[j].catre] == -1)
            {
                cf[v[a].v[j].catre] = cf[a] + v[a].v[j].cost;
                h[lh] = v[a].v[j].catre;
                ph[v[a].v[j].catre] = lh;
                lh++;
                calib(lh - 1);
            }
            else if(cf[v[a].v[j].catre] > cf[a] + v[a].v[j].cost)
            {
                cf[v[a].v[j].catre] = cf[a] + v[a].v[j].cost;
                calib(ph[v[a].v[j].catre]);
            }
        }
    }
    for(i = 1; i < n; i++)
        if(cf[i] == -1)
            printf("0 ");
        else printf("%d ", cf[i]);
    return 0;
}