#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <limits.h>
#include <utility>
std::ifstream in("dijkstra.in");
std::ofstream out("dijkstra.out");
int cost[50001];
std::vector<std::pair<int,int> > v[50001];
std::priority_queue<std::pair<int,int> ,std::vector<std::pair<int,int> >,std::greater<std::pair<int,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(std::make_pair(b,c));
    }
    queue.push({1,0});
    while(!queue.empty()){
        std::pair<int,int> last=queue.top();
        for(auto pr:v[last.first])
            if(cost[pr.first]>cost[last.first]+pr.second)
                cost[pr.first]=cost[last.first]+pr.second,queue.push(std::make_pair(pr.first,cost[pr.first]));
        queue.pop();
    }
    for(int i=2;i<=n;i++)
        out<<cost[i]<<" ";

    return 0;
}