#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <limits.h>
std::ifstream in("dijkstra.in");
std::ofstream out("dijkstra.out");
std::vector<std::pair<int,int> >v[50001];
int cost[50001];
std::queue<int>queue;
int main()
{
    int n,m,a,b,c;
    in>>n>>m;
    for(int i=2;i<=n;i++)
        cost[i]=INT_MAX/2;
    for(int i=0;i<m;i++){
        in>>a>>b>>c;
        v[a].push_back({b,c});
    }
    queue.push(1);
    while(!queue.empty()){
        int last=queue.front();
        for(auto pr:v[last]){
            if(cost[pr.first]>cost[last]+pr.second)
                cost[pr.first]=cost[last]+pr.second;
            queue.push(pr.first);
        }
        queue.pop();
    }
    for(int i=2;i<=n;i++)
        out<<cost[i]<<" ";
    return 0;
}