#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m;
int distanta[50001], inCoada[50001];
vector < pair < int, int > > G[50001];
const int oo = 1e9;

struct compara {
    bool operator() (int x, int y) {
        return distanta[x] > distanta[y];
    }
};

priority_queue < int, vector < int >, compara > coada;

void dijkstra(int nod) {
    distanta[nod] = 0;
    coada.push(nod);
    inCoada[nod] = true;
    while (!coada.empty()) {
        int nod_curent = coada.top();
        coada.pop();
        inCoada[nod_curent] = false;
        for (unsigned int i = 0; i < G[nod_curent].size(); ++i) {
            int vecin = G[nod_curent][i].first;
            int cost = G[nod_curent][i].second;
            if (distanta[nod_curent] + cost < distanta[vecin]) {
                distanta[vecin] = distanta[nod_curent] + cost;
                if (inCoada[vecin] == false) {
                    inCoada[vecin] = true;
                    coada.push(vecin);
                }
            }
        }
    }

}

int main() {
    fin >> n >> m;
    int a, b, c;
    for (int i = 1; i <= m; ++i) {
        fin >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
    }
    for (int i = 1; i <= n; ++i)
        distanta[i] = oo;
    dijkstra(1);
    for (int i = 2; i <= n; ++i) {
        if (distanta[i] != oo)
            fout << distanta[i] << " ";
        else
            fout << "0 ";
    }

}