#define MAXN 50005
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

int N, M, source_node, destination_node, edge_length;
long long D[MAXN];

queue <int> Q;

vector < pair <int,int> > edges[MAXN];

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

int main(){

    fin >> N >> M;

    while( M -- ){

        fin >> source_node >> destination_node >> edge_length;

        edges[source_node].push_back(make_pair(destination_node, edge_length));

    }

    for(int i = 2; i <= N; i ++)
        D[i] = LONG_LONG_MAX;

    Q.push(1);

    while( !Q.empty() ){

        int node = Q.front();
        int dist = D[node];

        Q.pop();

        for(vector < pair <int, int> >::iterator it = edges[node].begin(); it != edges[node].end(); it ++){

            if(D[it->first] > dist + it->second){

                D[it->first] = dist + it->second;
                Q.push(it->first);

            }

        }

    }

    for(int i = 2 ; i <= N ; i ++)
        fout << D[i] << " ";

    fout << "\n";


}