#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int INF=INT_MAX/2;
int main()
{
   int n , m;
   fin>>n>>m;
   vector<vector<pair<int,int>>> adj(n+1);
   ///.first reprezinta nodul vecin
   ///.second reprezinta costul
   for(int i = 0; i < m; i++)
   {
       int a , b ,c ;
       fin>>a>>b>>c;
       adj[a].push_back({b,c});
   }
   vector <int> dist(n+1,INF);
   dist[1]=0;
    priority_queue<
    pair<int,int>,  // .first==dist
    vector<pair<int,int>>,
    greater<pair<int,int>>> q;
   q.push({dist[1],1});
   while(!q.empty())
   {
       int nod=q.top().second;
       int d=q.top().first;
       q.pop();
       if(d!=dist[nod])continue;
       for(auto p : adj[nod])
       {
           int v=p.first;
           int c=p.second;
           if(dist[nod]+c<dist[v])
           {
               dist[v]=dist[nod]+c;
               q.push({dist[v],v});
               
           }
       }
   }
   for(int i=2;i <= n;i++)
   {
       if(dist[i]=INF)fout<<0<<' ';
       else fout<<dist[i]<<' ';
   }
   fout<<"\n";
}