#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;
const int NMAX = 5e4 + 5;
int cmp ( pair <int,int> a , pair <int,int > b)
{
    return (a>b);
}
priority_queue <pair < int ,int >  > Q;
int n, m ,i , x , y , cost , f[NMAX] , nod , ok;
vector <pair <int,int> > a[NMAX];
pair <int,int > p;
int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin >> n >> m;
    for(i=1;i<=m;i++)
    {
        fin >> x >> y >> cost;
        a[x].push_back({y,-cost});
    }
    Q.push({0  , 1});
    while(!Q.empty() )
    {
        p = Q.top();
        Q.pop();
        nod = p.S;
        cost = p.F;
        if(f[nod] != 0){continue;}
        f[nod] = cost;
        if(nod == 1)f[nod] = 1;
        for(i=0;i<a[nod].size();i++)
            Q.push({a[nod][i].S + cost , a[nod][i].F});
    }
    for ( i=2; i<=n; i++)
        fout << -f[i] << " ";
    return 0;
}