#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];
bool viz[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({0,1});
    while(!queue.empty()){
        std::pair<int,int> last=queue.top();
        queue.pop();
        if(viz[last.second])
            continue;
        viz[last.second]=1;
        for(auto pr:v[last.second])
            if(!viz[pr.first] && cost[pr.first]>cost[last.second]+pr.second)
                cost[pr.first]=cost[last.second]+pr.second,queue.push(std::make_pair(cost[pr.first],pr.first));
    }
    for(int i=2;i<=n;i++)
        out<<((cost[i]!=INT_MAX/2)?cost[i]:0)<<" ";

    return 0;
}