#include <bits/stdc++.h>

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int l[50001];
vector<pair<int,int>>v[50001];
struct compare
{
    bool operator ()(const pair<int,int>&a, const pair<int,int>&b)
    const
    {
        return (a.second>b.second || (a.second==b.second && a.first>b.first));
    }
};
void ff(int i)
{
    priority_queue<pair<int,int>,vector<pair<int,int>>,compare>q;
    q.push({i,0});
    int val;
    while(!q.empty())
    {
        i=q.top().first,val=q.top().second;
        q.pop();
        if(l[i])
            continue;
        l[i]=val;
        for(int j=0;j<v[i].size();j++)
            if(!l[v[i][j].first])
                q.push({v[i][j].first,val+v[i][j].second});
    }
}
int main()
{
    int n,m,val,a,b;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>val;
        v[a].push_back({b,val});
    }
    ff(1);
    for(int i=2;i<=n;i++)
        fout<<l[i]<<' ';
    return 0;
}