#include <fstream>
#include <vector>
#include <set>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

#define Max 99999999999
#define f first
#define s second

struct adat
{
    bool l;
    long long hossz=Max;
    vector<pair<int,int>>ut;
};
vector<adat>x;

struct uthossz
{
    long long hova, ut;
};

bool operator< (const uthossz &a, const uthossz &b)
{
    return a.ut<b.ut || a.ut==b.ut && x[a.hova].l>x[b.hova].l;
}

long long n,m,a,b,c,i;

int main()
{
    cin>>n>>m;
    x.resize(n+1);
    for(i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        x[a].ut.push_back({b,c});
        //x[b].ut.push_back({a,c});
    }

    set<uthossz>s;
    set<uthossz> :: iterator it;
    set<uthossz> :: iterator it2;

    s.insert({1,0});
    it=s.begin();

    while(it!=s.end())
    {
        x[it->hova].l=true;
        x[it->hova].hossz=it->ut;

        for(auto e : x[it->hova].ut)
        if(!x[e.f].l && x[e.f].hossz>(e.s+x[it->hova].hossz))
        {
            it2=s.find({e.f,x[e.f].hossz});
            if(it2!=s.end()) s.erase(it2);
            x[e.f].hossz=e.s+x[it->hova].hossz;
            s.insert({e.f,x[e.f].hossz});
        }

        it++;
    }

    for(i=2;i<=n;++i)
    if(x[i].hossz==Max) cout<<"0 ";
    else cout<<x[i].hossz<<" ";

    return 0;
}