#include <set>
#include <fstream>
#include <queue>
#include <list>
#define inf 2147000000

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct graf{
    int info;
    list<pair<int, int> > cost;
} v[50002];

class comp{
public:
    bool operator()(pair<int, int> p1, pair<int, int> p2){
        return p1.second > p2.second;
    }
};

int _d_a_b(int a, int b)
{
    list<pair<int, int> >::iterator s;
    s = v[a].cost.begin();
    while(s != v[a].cost.end()){
        if((*s).first == b) return (*s).second;
        s++;
    }

    return inf;
}

void distmin(int n, int rn)
{
    int d[50002]; bool sel[50002] = {0};
    int i, a, b, ct = 1; sel[1] = 1;

    priority_queue<pair<int, int>, vector<pair<int, int> >, comp> pq;

    for(i = 2; i <= 50000; i++) d[i] = inf;d[1] = 0;

    list<pair<int, int > >::iterator s;
    s = v[1].cost.begin();
    while(s != v[1].cost.end())
        d[(*s).first] = (*s).second, pq.push(*s), s++;

    while(!pq.empty() && ct <= rn)
    {
        a = pq.top().first, b = pq.top().second, pq.pop();
        if(sel[a] == 1) continue;
        sel[a] = 1, ct++;
        s = v[a].cost.begin();

        while(s != v[a].cost.end()){
            if(!sel[(*s).first] && ( d[(*s).first] > _d_a_b(a, (*s).first) + b ) )
                d[(*s).first] = _d_a_b(a, (*s).first) + b,
                pq.push(make_pair((*s).first, d[(*s).first]));
            s++;
        }
    }
    for(i = 2; i <= n; i++){
        if(d[i] == inf) fout << 0 << " ";
            else fout << d[i] << " ";
    }

}

int howMany_reachableNodes(int n)
{
    int ct = 1;
    graf aux[50001];

    for(int i = 1; i <+ n; i++)
        aux[i] = v[i];

    queue<graf> q;
    list<pair<int, int> > l;
    set<int> s;

    q.push(aux[1]);
    while(!q.empty())
    {
        l = q.front().cost;q.pop();
        while(!l.empty()){
            if(s.find(l.front().first) == s.end())
            q.push(aux[l.front().first]),
                ct++, s.insert(l.front().first);
            l.pop_front();
        }
    }
    return ct;
}

int main()
{
    int i, a, b, x, n, m;
    fin >> n >> m;
    for(i = 1; i <= m; i++){
        fin >> a >> b >> x;
        v[a].cost.push_back(make_pair(b, x));
        v[a].info = a;
    }

    m = howMany_reachableNodes(n);

    distmin(n, m);
    return 0;
}