#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <utility>

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

struct Edge
{
    int cost,nod;
    Edge(int cost1,int nod1);
};

Edge::Edge(int cost1,int nod1)
{
    cost=cost1;
    nod=nod1;
}

int main()
{
    int n,m,i,j,c,a,b,inf,ind;
    f>>n>>m;

    inf=(n-1)*20000;
    vector<int>d(n+1,inf);
    vector<vector<Edge>>G(n+1);
    set<pair<int,int>>S;

    S.insert(make_pair(0,1));
    d[1] = 0;
    for(i=1; i<=m; i++)
    {
        f>>a>>b>>c;
        G[a].push_back(Edge(c,b));
    }

    for(i=1; i<n; i++)
    {
        if(S.empty())
            break;
        ind=(*S.begin()).second;
        S.erase(S.begin());

        for(auto edge:G[ind])
            if(d[edge.nod]>d[ind]+edge.cost)
            {
                S.erase(make_pair(d[edge.nod],edge.nod));
                d[edge.nod]=d[ind]+edge.cost;
                S.insert(make_pair(d[edge.nod],edge.nod));
            }
    }

    for(i=2; i<=n; i++)
    {
        if(d[i]==inf)
            d[i]=0;
        g<<d[i]<<" ";
    }
}