#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
vector<pair<int,int>>v[50005];
bool f[50005];
int rez[50005];
int main()
{
   int n,m,c,a,b;
   cin>>n>>m;
   for(int i=0;i<m;i++)
   {
       cin>>a>>b>>c;
       v[a].push_back({b,c});
   }
   priority_queue<pair<int,int>>pq;
   pq.push({0,1});
   while(!pq.empty())
   {
       int nd=pq.top().second,cst=-pq.top().first;
       pq.pop();
       if(f[nd]==1)
           continue;
        f[nd]=1;
        rez[nd]=cst;
        for(auto i:v[nd])
        {
            if(f[i.first]==0)
            {
                pq.push({-i.second-cst,i.first});
            }
        }
   }
   for(int i=2;i<=n;i++)
    cout<<rez[i]<<" ";
    return 0;
}