#include <iostream>
#include <set>
#include <vector>
#include <limits.h>
#include <set>
#include <fstream>

using namespace std;

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

int N, M;
int from, to, weight;

vector<int> dist(50001, INT_MAX);
vector < pair <int, int> > emptyVec;
vector< vector< pair<int, int> > >graph(50001, emptyVec);

void addEdge(int from, int to, int weight){
    graph[from].push_back( make_pair(to,weight) );
}

void shortestPath(int startNode, int N){
    set< pair<int,int> > minSet;
    minSet.insert(make_pair(0,startNode));
    dist[startNode] = 0;
    while(!minSet.empty()){
        pair<int,int> temporary = *( minSet.begin() );
        minSet.erase(minSet.begin());
        int currentNode = temporary.second;
        for(int i = 0; i < graph[currentNode].size(); i++){
            int node = graph[currentNode][i].first;
            int weight = graph[currentNode][i].second;
            if(dist[node] > dist[currentNode] + weight){
                if(dist[node] != INT_MAX)
                    minSet.erase(minSet.find(make_pair(dist[node], node)));
                dist[node] = dist[currentNode] + weight;
                minSet.insert(make_pair(dist[node], node));
            }
        }
    }
    for(int i = 2; i <= N; i++){
        if(dist[i] == INT_MAX)
            g << 0 <<" ";
        else
            g << dist[i] << " ";
    }
}

int main()
{
    f >> N >> M;
    for(int i = 0; i < M; i++){
        f >> from >> to >> weight;
        addEdge(from, to, weight);
    }
    shortestPath(1, N);
}