#include <bits/stdc++.h>

#define NMAX 50000
#define INF 999999999

using namespace std;

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

int n,m;
vector <pair<int,int> > G[NMAX+5];
int dist[NMAX+5];
set <pair< int,int> > h;

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int from,to,cost;
        f>>from>>to>>cost;
        G[from].push_back({to,cost});
    }

    for(int i=1; i<=n; i++)
        dist[i]=INF;

    dist[1]=0;
    h.insert({0,1});

    while(!h.empty())
    {
        int node=h.begin()->second;
        h.erase(h.begin());
        for(auto it : G[node])
        {
            int to=it.first;
            int cost=it.second;
            if(dist[to] > dist[node]+cost)
            {
                if(dist[to]!=INF)
                    h.erase(h.find({dist[to],to}));
                dist[to]=dist[node]+cost;
                h.insert({dist[to],to});

            }
        }
    }

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


}