#include <fstream>
#include <algorithm>
#include <set>
#include <vector>
#define MaxNumerOfNodes 50005
#define INF (1 << 30)
using namespace std;

ifstream cin("dijkstra.in");
ifstream cout("dijkstra.out");

vector < pair < int , int > > Graph[MaxNumerOfNodes];
set < pair <int,int> > Set;
set < pair < int , int > > :: iterator it;
int N, M, Distance[MaxNumerOfNodes];

void Dijkstra(int node)
{
    int currentNode, cost, nextNode, nextCost;
    Set.insert(make_pair(0,node));
    Distance[node] = 0;
    while(!Set.empty()){
        it = Set.begin();
        Set.erase(Set.begin());
        cost = (*it).first;
        currentNode = (*it).second;
        if(cost > Distance[currentNode]){
            continue;
        }
        for(int i = 0; i < Graph[currentNode].size(); i++){
            nextNode = Graph[currentNode][i].second;
            nextCost = Graph[currentNode][i].first;
            if(Distance[nextNode] > Distance[currentNode] + nextCost){
                Distance[nextNode] = Distance[currentNode] + nextCost;
                Set.insert(make_pair(Distance[nextNode],nextNode));
            }
        }
    }
}

int main()
{
    int startingNode = 1;
    int nodeX, nodeY, costRoad;
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        cin >> nodeX >> nodeY >> costRoad;
        Graph[nodeX].push_back(make_pair(costRoad,nodeY));
    }
    for(int i = 1; i <= N; i++){
        Distance[i] = INF;
    }
    Dijkstra(startingNode);
    for(int i = 2; i <= N; i++){
        cout << Distance[i] << " ";
    }
    return 0;
}