#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, x, y, z, i;

vector < pair<int, int> > v[50001];
int d[50001];
int viz[50001];

class cmp {
public:
    bool operator () (int a, int b) {
        return d[a] > d[b];
    }
};

// tipul de elemente din pq, vector<tip>, cmp
priority_queue<int, vector<int>, cmp> pq;

void dijkstra() {
    for(i = 2; i <= n; i ++)
        d[i] = INT_MAX;
    pq.push(1);
    viz[1] = 1;
    d[1] = 0;
    while(!pq.empty()) {
        int nod = pq.top(); // nod = 2
        for(auto u : v[nod]) { // v[2]
            // u.first = 3, u.second = 2
            if(d[nod] + u.second < d[u.first])
                d[u.first] = d[nod] + u.second;
            if(viz[u.first] == 0) {
                viz[u.first] = 1;
                pq.push(u.first);
            }
        }
        pq.pop();
    }
}

int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i ++) {
        f >> x >> y >> z;
        v[x].push_back({y, z});
    }
    dijkstra();
    for(i = 2; i <= n; i ++) {
        if(d[i] == INT_MAX)
            g << 0 << ' ';
        else
            g << d[i] << ' ';
    }

    f.close();
    g.close();
    return 0;
}