#include <fstream>
#include <vector>
#include <queue>

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;
};

struct uthossz
{
    long long hova, ut;
};
uthossz q;

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

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

int main()
{
    cin>>n>>m;
    vector<adat>x(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});
    }

    priority_queue<uthossz>que;

    que.push({1,0});

    while(!que.empty())
    {
        q=que.top();
        while(x[q.hova].l)
        {
            que.pop();
            if(!que.empty()) q=que.top();
            else break;
        }

        if(que.empty()) break;
        que.pop();

        x[q.hova].l=true;
        x[q.hova].hossz=q.ut;

        for(auto e : x[q.hova].ut)
        if(!x[e.f].l && x[e.f].hossz>(e.s+x[q.hova].hossz))
        {
            x[e.f].hossz=e.s+x[q.hova].hossz;
            que.push({e.f,x[e.f].hossz});
        }
    }

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

    return 0;
}