//n^2 < m*log(n)
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMax = 5 * 1e4, oo = 0x3f3f3f3f;

vector <pair<int, int>> g[NMax + 5];

int n, m;
bool use[NMax + 5];
int dist[NMax + 5];

void Read(){
    fin >> n >> m;
    while (m--){
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back(make_pair(b, c));
    }
}

void Dijkstra(){
    for (int i = 2; i <= n; i++)
        dist[i] = oo;

    for (int i = 1; i <= n; i++){
        int minval = oo, node = 0;
        for (int j = 1; j <= n; j++)
            if (dist[j] < minval && !use[j]){
                minval = dist[j];
                node = j;
            }
        for (auto ngh : g[node])
            dist[ngh.first] = min(dist[ngh.first], minval + ngh.second);
        use[node] = 1;
    }

    for (int i = 1; i <= n; i++)
        if (dist[i] == oo)
            dist[i] = 0;
}

void Print(){
    for (int i = 2; i <= n; i++)
        fout << dist[i] << ' ';
    fout << '\n';
}

int main(){
    Read();
    Dijkstra();
    Print();
    return 0;
}