#include <bits/stdc++.h>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct drumuri{
    int node,cost;
};

struct compare{
    bool operator()(drumuri a,drumuri b){
        return a.cost>b.cost;
    }
};

int n,m,x,y,z,drum[50200];
vector <drumuri> edges[50200];
priority_queue <drumuri, vector<drumuri>, compare> pq;

void dijkstra()
{
    for(int i=1; i<=n; i++)
        drum[i]=INT_MAX;
    drum[1]=0, pq.push({1,0});
    while(!pq.empty())
    {
        drumuri x=pq.top();
        pq.pop();
        if(x.cost==drum[x.node])
            for(auto y:edges[x.node])
                if(x.cost+y.cost<drum[y.node])
                    drum[y.node]=x.cost+y.cost, pq.push({y.node,drum[y.node]});
    }
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>x>>y>>z, edges[x].push_back({y,z});
    dijkstra();
    for(int i=2; i<=n; i++)
        if(drum[i]==INT_MAX)
            g<<0<<' ';
        else
            g<<drum[i]<<' ';
    return 0;
}