#include <fstream>
#include<queue>
#include<vector>
#include<climits>
using namespace std;
struct elem{
   int x,c;
};
bool viz[50001];
class cmp{
public:
 bool operator() (const elem &a, const  elem &b) {
    return a.c>b.c;
 }
};
priority_queue <elem, vector <elem>, cmp> heap;
int d[50001],n,m;
vector <elem> g[50001];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int main()
{
    int i,x,y,c;

fin>>n>>m;
for(i=1;i<=m;i++){
    fin>>x>>y>>c;;
    g[x].push_back({y,c});
}
for(int i=2;i<=n;i++)
     d[i]=INT_MAX;
heap.push({1,0});
while(!heap.empty()){
    int nod=heap.top().x;
    int c=heap.top().c;
        heap.pop();
    if(viz[nod]==1)
        continue;
    viz[nod]=1;

    for(int i=0;i<g[nod].size();i++){
        int nodv=g[nod][i].x;
        int cost=g[nod][i].c;
        if(viz[nodv]==0&&d[nodv]>c+cost){
           d[nodv]=d[nod]+cost   ;
           heap.push({nodv,d[nodv]});
        }
    }

}
for(int i=2;i<=n;i++)
    if(d[i]!=INT_MAX)
        fout<<d[i]<<" ";
else
    fout<<0<<" ";
    return 0;
}