#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#define dMAX 50000
#define INF 999999

using namespace std;

int n, m, x, y, c;
vector<pair<unsigned short int, int> > graf[dMAX + 2];
bool viz[dMAX + 2];
int dij[dMAX + 2];

deque<int> myDeque;
int pVerif, newV;

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

int main()
{
    int i, j;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        graf[x].push_back({y, c});
    }
    viz[1] = true;
    myDeque.push_back(1);
    while (!myDeque.empty()) {
        pVerif = myDeque.front();
        myDeque.pop_front();
        for (i = 0; i < graf[pVerif].size(); i++) {
            newV = graf[pVerif][i].first;
            if (!viz[newV]) {
                dij[newV] = graf[pVerif][i].second + dij[pVerif];
                myDeque.push_back(newV);
                viz[newV] = true;
            } else
                if (dij[newV] > dij[pVerif] + graf[pVerif][i].second) {
                    dij[newV] = graf[pVerif][i].second + dij[pVerif];
                    myDeque.push_back(newV);
                    viz[newV] = true;
                }
        }
    }

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

    return 0;
}