#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

struct Pair {
    int w, x;
    bool operator < (const Pair & A) const {
        return w > A.w;
    }
};

const int INF = 0x3f3f3f3f;
int n, m;
vector<vector<pair<int, int>>> G;
vector<int> D;

void Read();
void Dijkstra(int S, vector<int> & d);
void Write();

int main() {
    Read();
    Dijkstra(1, D);
    Write();
    fin.close();
    fout.close();
    return 0;
}

void Dijkstra(int S, vector<int> & d) {
    priority_queue<Pair> Q;
    d[S] = 0;
    Q.push({0, S});
    int x, dx, y, w;
    while (!Q.empty()) {
        x = Q.top().x;
        dx = Q.top().w;
        Q.pop();
        if (d[x] < dx) continue;
        for (const auto & e : G[x]) {
            y = e.first; w = e.second;
            if (d[y] > d[x] + w) {
                d[y] = d[x] + w;
                Q.push({d[y], y});
            }
        }
    }
}

void Write() {
    for (int i = 2; i <= n; i++)
        if (D[i] == INF) fout << "0 ";
        else fout << D[i] << ' ';
}

void Read() {
    fin >> n >> m;
    G = vector<vector<pair<int, int>>>(n + 1);
    D = vector<int>(n + 1, INF);
    for (int i = 0, x, y, w; i < m; i++) {
        fin >> x >> y >> w;
        G[x].push_back({y, w});
    }
}