#include <fstream>
#include <vector>
#include <set>
using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
#define int long long
vector<pair<int,int>> v[50001];
int min1[50001],n,m;
set<pair<int,int>> s;

void dij(int poz){
    int i,cnt=1,nod,minc;
    for(i=1;i<=n;i++){
        min1[i]=1e18;
        if(i!=poz) s.insert({1e18,i});
    }
    min1[poz]=0;s.insert({0,poz});
    while(!s.empty()){
        auto it=s.begin();s.erase(s.begin());
        nod=(*it).second;minc=(*it).first;
        for(auto it:v[nod]){
            if(min1[it.first]>minc+it.second){
                s.erase({min1[it.first],it.first});
                min1[it.first]=minc+it.second;
                s.insert({min1[it.first],it.first});
            }
        }
    }
    for(i=2;i<=n;i++) cout<<min1[i]<<" ";
}

signed main()
{
    int i,a,b,c;
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>a>>b>>c;
        v[a].push_back({b,c});
    }
    dij(1);
    return 0;
}