#include <fstream>
#include <vector>
#include <queue>
#define MAX 100001
#define inf 1<<30
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct heap{
    int nod,cost;
    bool operator < (const heap &x)const{
       return cost>x.cost;
    }
};
priority_queue<heap>h;
struct nod{int nod,cost;};
vector<nod> a[MAX];
vector<nod>::iterator it;
int n,m,p;
int d[MAX];
void citire(){
   f>>n>>m;
   int x,y,z;
   for(int i=1 ; i<=m ; ++i)
   {
       f>>x>>y>>z;
       a[x].push_back({y,z});
   }
}
void dijkstra(int x){
    for(int i=1 ; i<=n ; ++i)
        d[i]=inf;
    d[x]=0;
   int dist,k,D;
   h.push({x,0});
   while(!h.empty())
   {
       k=h.top().nod;
       D=h.top().cost;
       h.pop();
       if(d[k]==D)
       {
           vector<nod>::iterator sf=a[k].end();
           for(it=a[k].begin() ; it!=sf ; ++it)
       {
           dist=d[k]+it->cost;
           if(d[it->nod]>dist)
           {
               d[it->nod]=dist;
               h.push({it->nod,dist});
           }
       }
       }

   }
}
void afis(){
   for(int i=2 ; i<=n ; ++i)
        if(d[i]==inf)
          g<<0<<" ";
        else
          g<<d[i]<<" ";
    g<<'\n';
}
int main()
{
    citire();
    dijkstra(1);
    afis();
    return 0;
}