#include <fstream>
#include <vector>
#define inf 1e9
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair<int,int>> v[50005];
int d[50005],f[50005],N,M;
pair<int,int> a;
void Relaxare(int nod)
     {int i,mn=inf,p=0;
      f[nod]=1;
      for(i=0;i<v[nod].size();i++)
         if(d[v[nod][i].first]>v[nod][i].second+d[nod]){d[v[nod][i].first]=v[nod][i].second+d[nod];}
      for(i=2;i<=N;i++)
      if(f[i]==0&&mn>d[i]){mn=d[i];p=i;}
      if(p!=0)Relaxare(p);
     }
int main()
{int i,x,y,z;
 fin>>N>>M;
 for(i=1;i<=M;i++)
    {fin>>x>>y>>z;
     a.first=y;
     a.second=z;
     v[x].push_back(a);
    }
 d[1]=0;
 for(i=2;i<=N;i++)
    {d[i]=inf;
    }
 Relaxare(1);
 for(i=2;i<=N;i++)
 {if(d[i]!=inf)fout<<d[i]<<" ";
  else fout<<"0 ";
 }
}