#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <string.h>
#include <queue>
#include <bits/stdc++.h>
#define dMAX 50000
#define INF 999999999

using namespace std;

int n, m, x, y, c;
vector<pair<int, int> > graf[dMAX + 2];
bool viz[dMAX + 2];
long long int dij[dMAX + 2], t, len, s;

char nr[30];

struct Compare{
    bool operator() (int e1, int e2) {
        return dij[e1] > dij[e2];
    }
};

priority_queue<int, vector<int>, Compare> myDeque;
int pVerif, newV;

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

int Nr(int &i) {
    t = 0;
    while (isdigit(nr[i])) {
        t *= 10;
        t += (int)nr[i] - '0';
        i++;
    }
    i++;
    return t;
}

int main()
{
    int i, j;
    fin >> n >> m;
    fin.get();
    for (j = 1; j <= m; j++) {
        fin.getline(nr, 30);
        i = 0;
        x = Nr(i);
        y = Nr(i);
        c = Nr(i);
        graf[x].push_back({y, c});
    }
    for (i = 1; i <= n; i++) dij[i] = INF;
    dij[1] = 0;
    viz[1] = true;
    myDeque.push(1);
    while (!myDeque.empty()) {
        pVerif = myDeque.top();
        viz[pVerif] = false;
        myDeque.pop();
        s = graf[pVerif].size();
        for (i = 0; i < s; i++) {
            newV = graf[pVerif][i].first;
                if (dij[pVerif] + graf[pVerif][i].second < dij[newV]) {
                    dij[newV] = dij[pVerif] + graf[pVerif][i].second;
                    if (!viz[pVerif]) {
                        myDeque.push(newV);
                        viz[newV] = true;
                    }
                }
        }

    }

    for (i = 2; i <= n; i++) {
        if (dij[i] != INF)
        fout << dij[i] << ' ';
        else fout << 0 << ' ';
    }

    return 0;
}