#include <fstream>
#include <vector>
#include <set>
#define X first
#define Y second
#define PII pair<int, int>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int N = 50005, f_mare = 2e9;
int cost[N];
struct edge {
    int y, c;
};
vector <edge> ls[N];
set<PII> coada;
int n, m, x, y, c, i, j;

void dijkstra(int x) {
    PII k, l;
    for (i = 2; i <= n; i++)
        cost[i] = f_mare;
    coada.insert({0,1});
    while (coada.empty() == 0) {
        k = *(coada.begin());
        coada.erase(coada.begin());
        for (auto l : ls[k.Y]) {
            if (cost[k.Y] + l.c < cost[l.y]) {
                if (coada.find( {cost[l.y], l.y} ) != coada.end())
                    coada.erase({cost[l.y], l.y} );
                cost[l.y] = cost[k.Y] + l.c;
                coada.insert( {cost[l.y], l.y} );
            }
        }
    }
}

int main() {
    f >> n >> m;
    while (m--) {
        f >> x >> y >> c;
        ls[x].push_back({y,c});
    }
    dijkstra(1);
    for (i = 2; i <= n; i++)
        if (cost[i] == f_mare) g <<"0 ";
        else g << cost[i] << ' ';
}