/// VARIANTA MEA, RAMANE DE VAZUT DC E MAI INEFICIENTA
#include <set>
#include <fstream>
#include <queue>
#include <list>
#define inf 2147000000

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

list<pair<int, int> > v[50002];

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

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

    for(i = 1; i <= n; i++) d[i] = inf;
    priority_queue<pair<int, int>, vector<pair<int, int> >, comp> pq;
    list<pair<int, int > >::iterator s;
    pq.push(make_pair(1, 0));

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

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

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

    distmin(n);
    return 0;
}