#include<fstream>
#include<vector>
#include<queue>
#define inf 2000000000
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int,int>>g[50001];
int d[50001],n,m,i,x,y,c,viz[50001];
struct cmp{
 bool operator () (const int &a, const int &b) const{
     return d[a]>d[b];

 }


};
priority_queue<int ,vector<int>, cmp>h;
int main () {
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));

    }
    d[1]=0;
    for(i=2;i<=n;i++)
        d[i]=inf;
    h.push(1)  ;
while(!h.empty()){

int    nod=h.top();

     h.pop();
     if(viz[nod]==0){
              viz[nod]=1;
     for(i=0;i<g[nod].size();i++)
         if(viz[g[nod][i].first]==0&&d[g[nod][i].first]>d[nod]+g[nod][i].second){
              d[g[nod][i].first]=d[nod]+g[nod][i].second;
              h.push(g[nod][i].first);
       viz[g[nod][i].first]=0;
     }



     }

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