#include<fstream>
#include<iostream>
#include<set>
#include<vector>
#define inf 2<<19
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int x,y,c,d[5005],valoare;
unsigned int i,n,m;
vector<int> a[5005],C[5005];
set<pair<int,int>> cost_nod;

int main()
   {
       f>>n>>m;
       for (i=1;i<=m;i++)
       { f>>x>>y>>c;
         a[x].push_back(y);
         C[x].push_back(c);}

       for (i=2;i<=n;i++)
            d[i]=inf;
      cost_nod.insert(make_pair(0,1));

      while(cost_nod.size()>0){
       valoare=(*cost_nod.begin()).first;  x=(*cost_nod.begin()).second;
      cost_nod.erase(*cost_nod.begin());
       for (i=0;i<a[x].size();i++)
            if (d[a[x][i]]>valoare+C[x][i])
                 d[a[x][i]]=valoare+C[x][i],  cost_nod.insert(make_pair(d[a[x][i]],a[x][i]));
     }

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