/// Craciun Catalin
///  Implementare Dijkstra - set
#include <iostream>
#include <fstream>
#include <set>
#include <vector>

#define inf 1<<30
#define NMax 200005
#define mp(x,y) make_pair(x,y)
#define pb(x,y) push_back(x,y)

using namespace std;

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

int n,m;
vector<int> V[NMax], C[NMax];
int d[NMax];
set < pair<int, int> > B;

void dijkstra_set() {
/*
    for (int i=2;i<=n;i++)
        d[i] = inf;

    B.insert(mp(0,1));

    while (!B.empty()) {
        int val = (*B.begin()).first, x = (*B.begin()).second;
        B.erase(*B.begin());
        for (int i=0;i<V[x].size();i++) {
            if (d[ V[x][i] ] > val + C[x][i]) {
                d[ V[x][i] ] = val + C[x][i];
                B.insert(mp(d[ V[x][i] ], V[x][i]));
            }
        }
    }*/

    int i, j, k, val, x;

    for(i = 2; i <= n; i++) d[i] = inf;
    B.insert( mp(0, 1) );

    while( B.size() > 0 )
    {
        val = (*B.begin()).first, x = (*B.begin()).second;
        B.erase(*B.begin());
        for(i = 0; i < V[x].size(); i++)
         if(d[ V[x][i] ] > val + C[x][i] )
            d[ V[x][i] ] = val + C[x][i], B.insert(mp(d[V[x][i]],V[x][i]));
    }
}

int main() {

    f>>n>>m;

    for (int i=1;i<=n;i++) {
        int a,b,c;
        f>>a>>b>>c;
        V[a].push_back(b);
        C[a].push_back(c);
    }

    dijkstra_set();

    for (int i=2;i<n;i++) {
        if (d[i] == inf)
            g<<0<<' ';
        else
            g<<d[i]<<' ';
    }

    if (d[n] == inf)
        g<<0<<' ';
    else
        g<<d[n]<<' ';

    f.close(); g.close();

    return 0;
}