#include<bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int INF = 2000000000;
const int NMAX = 50001;

int N, M;
//vector < int > Ad[NMAX];
//vector < int > C[NMAX];

vector < pair < int, int > > Ad[NMAX];

priority_queue < pair < int, int > > H;

bool vis[NMAX];
int dist[NMAX];

void Dijkstra( int nod ){
    H.push(make_pair(0,nod));

    for( int i = 1; i <= N; ++i )
        if( i != nod )
            dist[i] = INF;

    while( !H.empty() ){

        int nod = H.top().second;
        int cost = H.top().first;
        H.pop();

        if( vis[nod] == 0 )
            vis[nod] = 1;
        else continue;

        for( int i = 0; i < Ad[nod].size(); ++i ){
            pair < int , int > w = Ad[nod][i];

            ///cout << nod << ' ' << w.second << ' ' << w.first << ' ' << dist[nod] << '\n';

            if( dist[w.second] > dist[nod] + w.first ){
                dist[w.second] = dist[nod] + w.first;
                H.push( make_pair(dist[w.second], w.second ));
            }
        }
    }
}
int main()
{
    fin >> N >> M;

    int x, y, c;
    for( int i = 1; i <= M; ++i ){
        fin >> x >> y >> c;
        Ad[x].push_back( make_pair(c,y) );
    }
    Dijkstra(1);

    for( int i = 2; i <= N; ++i)
        fout << dist[i] << ' ';
    fout << '\n';

    return 0;
}