#include <fstream>
#include<vector>
#include<queue>
#include<algorithm>
#include <cmath>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,D[100001];
bool InCoada[100001];
const int oo=1<<30;
vector<pair<int,int>>G[100001];
struct compara{
    bool operator()(int x,int y)
    {
        return D[x]>D[y];
    }
};
priority_queue<int,vector<int>,compara>Q;
int main()
{
   f>>n>>m;
   while(m--)
   {
       int x,y,c;
       f>>x>>y>>c;
       G[x].push_back(make_pair(y,c));
   }
   for(int i=1;i<=n;++i)
       D[i]=oo;D[1]=0;

   Q.push(1);
   InCoada[1]=true;
   while(!Q.empty())
   {
       int nodStart=Q.top();
       Q.pop();
       InCoada[nodStart]=false;
       for(int i=0;i<G[nodStart].size();++i)
       {
           int vecin=G[nodStart][i].first;
           int cost=G[nodStart][i].second;
           if(D[vecin]>D[nodStart]+cost) {
               D[vecin] = D[nodStart] + cost;
               if (!InCoada[vecin]) {
                   InCoada[vecin] = true;
                   Q.push(vecin);
               }
           }
       }
   }
   for(int i=2;i<=n;++i)
       if(D[i]!=(1<<30))
       g<<D[i]<<' ';
   else g<<0<<' ';
}