#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>

using namespace std;

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

const int NMAX = 50005;
const int INF = 1e9;

int n, m;
vector<pair<int , int>>graf[NMAX];
vector<int>dis(NMAX, INF);

struct cmp {
    bool operator()(pair<int, int> x, pair<int, int> y) {
        return x.first > y.first;
    }
};

void read() {
    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        graf[x].push_back(make_pair(y, c));
    }
}

void afis() {
    for (int i = 2; i <= n; i++) {
        fout << ((dis[i] != INF) ? dis[i] : 0) << ' ';
    }
}

void dijkstra() {
    dis[1] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>h;
    h.push(make_pair(0, 1));
    while (!h.empty()) {
        int cur = h.top().second;
        h.pop();

        for (const auto& i: graf[cur]) {
            int v = i.first;
            int cost = i.second;
            if (dis[v] > dis[cur] + cost) {
                if (dis[v] == INF) {
                    dis[v] = dis[cur] + cost;
                    h.push(make_pair(dis[v], v));
                }
            }
        }
    }
}

int main(){
    read();
    dijkstra();
    afis();
    return 0;
}