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

using namespace std;

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

struct Edge
{
    int nod,cost;
    Edge(int n,int c);
};

Edge::Edge(int n,int c)
{
    nod=n;
    cost=c;
}

int main()
{
    int n,m,a,b,cost;

    f>>n>>m;

    int inf=(n-1)*20000;
    vector<vector<Edge>> G(n+1);
    set<pair<int,int>> Q;
    vector<int> dist(n+1,inf);
    vector<int> viz(n+1,0);

    for (int i=0; i<m; i++)
    {
        f>>a>>b>>cost;
        G[a].push_back(Edge(b,cost));
    }

    int sursa=1;
    dist[sursa]=0;

    for (int i=1; i<=n; i++)
        Q.insert(make_pair(dist[i],i));

    while (!Q.empty())
    {
        int u=(*Q.begin()).second;
        Q.erase(Q.begin());

        for (auto v:G[u])
            if (dist[v.nod]>dist[u]+v.cost)
            {
                Q.erase(Q.find({dist[v.nod],v.nod}));
                dist[v.nod]=dist[u]+v.cost;
                Q.insert({dist[v.nod],v.nod});
            }
    }


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