#include <iostream>
#include <fstream>
#include <queue>
#include <climits>
#define ll long long

using namespace std;

ifstream beir("dijkstra.in");
ofstream kiir("dijkstra.out");

struct adat
{
    ll hossz = SHRT_MAX;
    vector < pair <ll,ll> > sz;
};

vector <adat> x;

struct tav
{
    ll hova, hossz;  
};

priority_queue <tav> t;

bool operator < (const tav& a, const tav& b)
{
    return a.hossz > b.hossz;
}

int main()
{
    ll csp, cs1, cs2, kolt, el;
    beir >> csp >> el;
    x.resize(csp+1);
    for(int i=1; i<=el; ++i)
    {
        beir >> cs1 >> cs2 >> kolt;
        x[cs1].sz.push_back({cs2, kolt});
    }
    beir.close();
    ll kezd = 1;
    t.push({1, 0});
    x[kezd].hossz = 0;
    tav akt;
    while(!t.empty())
    {
        akt = t.top();
        t.pop();
        for(auto &e : x[akt.hova].sz)
        {
            if(x[e.first].hossz > (akt.hossz + e.second))
            {
                x[e.first].hossz = akt.hossz + e.second;
                t.push({e.first, akt.hossz + e.second});
            }
        }
    }
    
    for(int i=2; i<=csp; ++i)
    {
        kiir << x[i].hossz << " ";
    }
    kiir.close();

    return 0;
}