#include<fstream>
#include<vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <int> l[9000];
vector <int> c[9000];
int v[9000],i,n,j,k,m,x1,y1,nr1,s[9000],p1,p2;
void bfs(int nod)
{
   v[nod]=1;
   int st=1;
   int dr=1;
   s[1]=nod;
   int sum=0;
   while(st<=dr)
   {
      int i=0;
      k=s[st];
      for(i=0;i<l[k].size();i++)
      if(v[l[k][i]]==0)
      {
         dr++;
         v[l[k][i]]=v[k]+c[k][i];
         s[dr]=l[k][i];
      }
      else
      if(v[k]+c[k][i]<v[l[k][i]])
      v[l[k][i]]=v[k]+c[k][i];
      st++;
   }
   for(i=2;i<=n;i++)
   g<<v[i]-1<<" ";
}
int main()
{
   f>>n>>m;
   int x1,y1,y2;
   for(i=1;i<=m;i++)
   {
      f>>x1>>y1>>y2;
      l[x1].push_back(y1);
      c[x1].push_back(y2);
   }
   bfs(1);
   return 0;
}