#include <iostream>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;ifstream fin("dijkstra.in");ofstream fout("dijkstra.out");struct qer{int x,y;};
struct comp{
    bool operator()(qer a,qer b){return a.y<b.y;}
};
vector<qer>v[50001];priority_queue<qer,vector<qer>,comp>q;
int n,m,i,a,b,c,afis[50001],x,y,x1,y1;
int main()
{
    fin>>n>>m;for(i=1;i<=m;i++){fin>>a>>b>>c;v[a].push_back({b,c});}
    q.push({1,0});for(i=2;i<=n;i++)afis[i]=1e9;
    while(!q.empty()){
        x=q.top().x;y=q.top().y;q.pop();
        for(i=0;i<v[x].size();i++)
        {
            x1=v[x][i].x;y1=v[x][i].y;
            if(y+y1<afis[x1]){
                afis[x1]=y+y1;q.push({x1,y+y1});
            }
        }

    }for(i=2;i<=n;i++)fout<<afis[i]<<' ';
    return 0;
}