#include <iostream>
#include <cstdio>
#include <vector>
#define NMax 50000
#define CostMax 1000000000
using namespace std;

struct edge
{
    int nod;
    int cost;

    edge(int n, int c)
    {
        nod = n;
        cost = c;
    }
};

struct path
{
    int nod;
    int cost;
    path(int n, int c)
    {
        nod = n;
        cost = c;
    }
};

class heap
{
    vector<path> h;
public:
    heap()
    {
        h.push_back(path(0, -1));
    }
    int empty()
    {
        if(h.size() == 1)
            return 1;
        return 0;
    }
    void push(path p)
    {
        h.push_back(p);
        int n = h.size() - 1;
        while(p.cost < h[n / 2].cost)
        {
            h[n] = h[n / 2];
            h[n / 2] = p;
            n /= 2;
        }
    }
    path pop()
    {
        path minim = h[1];
        int n = h.size() - 1;
        path p = h[n];
        h[1] = p;
        h.pop_back();
        --n;
        int poz = 1;
        while(poz <= n / 2)
        {
            if(2 * poz + 1 <= n)
            {
                if(p.cost < h[poz * 2].cost && p.cost < h[poz * 2 + 1].cost)
                    break;
                if(h[2 * poz].cost > h[2 * poz + 1].cost)
                {
                    h[poz] = h[2 * poz + 1];
                    h[2 * poz + 1] = p;
                    poz = poz * 2 + 1;
                }
                else
                {
                    h[poz] = h[2 * poz];
                    h[2 * poz] = p;
                    poz *= 2;
                }
            }
            else
            {
                if(h[2 * poz].cost < p.cost)
                {
                    h[poz] = h[2 * poz];
                    h[2 * poz] = p;
                    poz *= 2;
                }
            }

        }
        return minim;
    }
};

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n, m;
    vector<edge> graf[NMax + 1];

    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graf[a].push_back(edge(b, c));
    }
    vector<int> v(n + 1, 0);
    vector<int> cost(n + 1, CostMax);
    heap h;
    h.push(path(1, 0));

    while(!h.empty())
    {
        path p = h.pop();
        int nod = p.nod;
        v[nod] = 1;
        cost[nod] = p.cost;
        for(int i = 0; i < graf[nod].size(); ++i)
        {
            int nod2 = graf[nod][i].nod;
            if(!v[nod2])
            {
                int newCost = graf[nod][i].cost + cost[nod];
                if(newCost < cost[nod2])
                {
                    h.push(path(nod2, newCost));
                    cost[nod2] = newCost;
                }
            }
        }
    }

    for(int i = 2; i <= n; ++i)
        if(cost[i] != CostMax)
            cout << cost[i] << ' ';
        else
            cout << "0 ";

    return 0;
}