#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];

vector<int> h;
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(cf[a] < cf[tata(a)])
    {
        swap(cf[a], cf[tata(a)]);
        a = tata(a);
    }
}

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);
        cf[v[0].v[i].catre] = v[0].v[i].cost;
    }
    make_heap(h.begin(), h.end(), cmp);
    while(!h.empty())
    {
        a = h.front();
        pop_heap(h.begin(), h.end(), cmp);
        h.pop_back();
        //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.push_back(v[a].v[j].catre);
                push_heap(h.begin(), h.end(), cmp);
            }
            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(v[a].v[j].catre);
            }
        }
    }
    for(i = 1; i < n; i++)
        if(cf[i] == -1)
            printf("0 ");
        else printf("%d ", cf[i]);
    return 0;
}