#include <cstdio>
#include <vector>
#include <algorithm>
#define min(x,y) (x<y?x:y)

using namespace std;

struct Muchie
{
    int catre, cost;
};

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

vector<int> h;
int cf[50000] = {0};

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

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;
    for(i = 1; i < n; i++)
    {
        cf[i] = -1;
    }
    for(i = 0; i < m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        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);
    for(i = 1; i < n; i++)
    {
        a = h.front();
        pop_heap(h.begin(), h.end(), cmp);
        h.pop_back();
        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 cf[v[a].v[j].catre] = min(cf[v[a].v[j].catre], cf[a] + v[a].v[j].cost);
        }
    }
    for(i = 1; i < n; i++)
        printf("%d ", cf[i]);
    return 0;
}