#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream gout("dijkstra.out");
#define cout gout
const int NMAX=5e4, INF = INT_MAX;
bitset<NMAX> viz;

int main()
{
    int n, m;
    f >> n >> m;
    //initializam graful
    vector<vector<pair<int,int>>> g(n+1, vector<pair<int,int>>());
    //umplem vectorul de distante cu INF, inafara de primul nod
    vector<int> d(n+1, INF);
    priority_queue<pair<int,int>> pq;//se poate numi si heap

    d[1]=0;
    //citire
    for(int i=1; i<=m; i++)
    {
        int x, y, c;
        f >> x >> y >> c;
        g[x].push_back({y,c});
    }
    //in pq primul element este distanta negativa si al doilea este nodul
    //motivul e ca pq e sortat dupa primul element
    pq.push({0,1});
    while(!pq.empty())
    {
        int cnod = pq.top().second;
        //cand scoatem din pq punem - in fata
        int dist = -pq.top().first;
        pq.pop();
        if(viz[cnod]==0)
        {
            for(auto & vecin : g[cnod])
            {
                //daca distanta pana la vecin de pana acum e mai mare decat cea gasita acum
                //o schimbam
                if(d[vecin.first]>d[cnod]+vecin.second)
                {
                    d[vecin.first]=d[cnod]+vecin.second;
                    pq.push({-d[vecin.first],vecin.first});
                }
            }
            viz[cnod]=1;
        }
    }
    for(int i=2; i<d.size(); i++)
    {
        if(d[i]!=INF)
            cout << d[i] << " ";
        else cout << 0 << " ";
    }
}