#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
struct qer
{
    int dir, val;
};
struct comp
{
    bool operator() (qer a, qer b)
    {
        return a.val > b.val;
    }
};
int n, m, a, b, c, dst[50001], dir, val;bool  viz[50001];
vector<qer>v[50001];
priority_queue<qer, vector<qer>, comp>q;
int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> a >> b >> c;
        v[a].push_back ({b, c});
    }
    for (int i = 2; i <= n; i++) dst[i] = 1e9;
    q.push ({1, 0});
    while (!q.empty())
    {
        dir = q.top().dir;
        val = q.top().val;
        q.pop();
        if(viz[dir])continue;
        viz[dir]=1;dst[dir]=val;
        for(auto x:v[dir]){
            if(val+x.val<dst[x.dir]){
                q.push({x.dir,val+x.val});
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(dst[i]==1e9)dst[i]=0;
        cout<<dst[i]<<' ';
    }
    return 0;
}