#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int MAX = 50001;
const int oo = (1 << 30);
int n, m;
bool inCoada[MAX];
int d[MAX];
struct comparaDistante {
    bool operator()(int x, int y) {
        return d[x] > d[y];
    }
};
vector<pair<int, int>> g[MAX];
priority_queue<int, vector<int>, comparaDistante> coada;

void citire() {
    int i, x, y, c;

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

void dijkstra(int start) {
    int i, curent, vecin, cost;

    for (i = 1; i <= n; i++)
        d[i] = oo;

    d[start] = 0;
    coada.push(start);
    inCoada[start] = true;

    while (!coada.empty()) {
        curent = coada.top();
        coada.pop();

        inCoada[curent] = false;

        for (i = 0; i < g[curent].size(); i++) {
            vecin = g[curent][i].first;
            cost = g[curent][i].second;
            if (d[curent] + cost < d[vecin]) {
                d[vecin] = d[curent] + cost;
                if (inCoada[vecin] == false) {
                    coada.push(vecin);
                    inCoada[vecin] = true;
                }
            }
        }
    }
}

void afisare() {
    int i;

    for (i = 2; i <= n; i++)
        if (d[i] != oo)
            fout << d[i] << ' ';
        else 
            fout << 0 << ' ';
}

int main() {
    citire();
    dijkstra(1);
    afisare();

    fin.close();
    fout.close();

    return 0;
}