#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const long long int MAXN=100005,INF=1e9;
int n,m;
int cost[MAXN],frecv[MAXN];
vector<pair<int,int>> graf[MAXN];
void daijkstra(int nod)
{
    priority_queue<pair<int,int>> djk;///second - nod, first- cost pana la nod(minim curent)
    djk.push({0,nod});
    cost[nod]=0;
    while(!djk.empty())
    {
        int nownod=djk.top().second,nowcost=-djk.top().first;
        //cout<<nownod<<" costul curent=>"<<nowcost<<'\n';
        djk.pop();
        if(frecv[nownod])
            continue;
        frecv[nownod]=1;
        for(auto u:graf[nownod])///u.first- nodul, u.second- cost de la nownod la u-nod
        {
            if(nowcost+u.second<cost[u.first])
            {
                cost[u.first]=nowcost+u.second;
                djk.push({-cost[u.first],u.first});
            }
            //cout<<u.first<<" costul=>"<<cost[u.first]<<'\n';
        }
    }

}
int main()
{
    int ans=0,nod1,nod2,src,val;
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>nod1>>nod2>>val;
        graf[nod1].push_back({nod2,val});
    }
    for(int i=1;i<=n;++i)
        cost[i]=INF;
    daijkstra(1);
    for(int i=2;i<=n;++i)
    {
        fout<<cost[i]<<' ';
    }
    return 0;
}