#include <bits/stdc++.h>

#define cin fin
#define cout fout
#define int long long
using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int n,m;

int rez[50005];
vector<vector<pair<int,int>>>vc;
void Bfs(int x)
{
    priority_queue<pair<int,int>, vector <pair<int, int>>>q;
    q.push({-0,1});
    while(!q.empty())
    {
        int vl=q.top().first*-1;
        int poz=q.top().second;
        q.pop();
        for(int i=0;i<vc[poz].size();i++)
        {
            int poz2=vc[poz][i].first;
            if(rez[poz2]>vl+vc[poz][i].second)
            {
                rez[poz2]=vl+vc[poz][i].second;
                q.push({-rez[poz2],poz2});
            }
        }
    }

}
signed main()
{
   cin>>n>>m;
   vc.resize(n+1);
   for(int i=1;i<=n;i++)
    rez[i]=5000000005ll;
   for(int i=1;i<=m;i++)
   {
       int mds,mds2,val;
       cin>>mds>>mds2>>val;
       vc[mds].push_back({mds2,val});
       //vc[lin[i].b].push_back(i);
   }
   rez[1]=0;
   Bfs(1);
   for(int i=2;i<=n;i++)
   {
        if(rez[i]==5000000005ll)
            cout<<0<<" ";
        else
            cout<<rez[i]<<" ";
   }

    return 0;
}