#include <fstream>
#include <queue>

using namespace std;

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

const int MAX = 50001, inf = (1 << 30) - 1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
vector<pair<int, int>> v[MAX];
int n, m, d[MAX], viz[MAX];

void dijkstra(int source){
    for (int i = 1; i <= n; i++)
        d[i] = inf;
    d[source] = 0;

    q.push(make_pair(d[source], source));

    while (!q.empty()){
        int node = q.top().second;
        q.pop();

        if (viz[node])
            continue;
        else viz[node] = 1;

        for (auto it: v[node]){
            int ext = it.first, cost = it.second;
            if (d[node] + cost < d[ext])
                d[ext] = d[node] + cost;
            q.push(make_pair(d[ext], ext));
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int a, b, c; m; m--){
        fin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }

    dijkstra(1);

    for (int i = 2; i <= n; i++)
        fout << (d[i] == inf? 0 : d[i]) << ' ';

    return 0;
}