#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define INF 2100000000

using namespace std;

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

vector< pair<int, int> > v[50005];
set   < pair<int, int> > s;
int f[50005], d[50005];
int n, m, ii, jj, cc;
int nod;

int main (){
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        fin>>ii>>jj>>cc;
        v[ii].push_back( {jj, cc} );
    }

    for(int i=2; i<=n; i++)
        d[i]=INF;

    s.insert( {0, 1} );
    while(!s.empty()){
        nod=s.begin() -> second;
        s.erase(s.begin());

        for(int i=0; i<v[nod].size(); i++)
            if(d[ v[nod][i].first ] > d[nod] + v[nod][i].second){
                s.erase ( {d[ v[nod][i].first ], v[nod][i].first} );
                d[ v[nod][i].first ]=d[nod] + v[nod][i].second;
                s.insert( {d[ v[nod][i].first ], v[nod][i].first} );
            }
    }

    for(int i=2; i<=n; i++)
        if(d[i] == INF)
            fout<<0<<" ";
        else
            fout<<d[i]<<" ";
    return 0;
}