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

using namespace std;

const int NMAX = 1e5+9;

const int INF = 1e9+9;

#define pii pair<int,int>

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

int n,i,j,m,startnode;

priority_queue<pii,vector<pii>,greater<pii>>q;

vector<pii>g[NMAX];

int cost[NMAX];

void dijkstra (int startnode);

signed main()
{
    fin>>n>>m;
    startnode=1;
    for (i=1; i<=m; i++)
    {
        int a,b,cost;
        fin>>a>>b>>cost;
        g[a].push_back ({b,cost});
    }
    dijkstra (startnode);
    for (i=2; i<=n; i++)
    {
        if (cost[i]!=INF)
        {
            fout<<cost[i]<<' ';
        }
        else
        {
            fout<<0<<' ';
        }
    }
    return 0;
}

void dijkstra (int startnode)
{
    for (i=1; i<=n; i++)
    {
        cost[i]=INF;
    }
    cost[startnode]=0;
    q.push({0,startnode});
    while (!q.empty ())
    {
        int node=q.top().second,currentcost=q.top().first;
        q.pop();
        for (auto it : g[node])
        {
            if (cost[it.first]>currentcost+it.second)
            {
                cost[it.first]=currentcost+it.second;
                q.push ({cost[it.first],it.first});
            }
        }
    }
}