#include <bits/stdc++.h>
#define MAX 50100
#define INF 1e9

using namespace std;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

vector < pair <long long, long long> > G[MAX];
long long d[MAX];
long long n,m;

void dostuff()
{
    fi>>n>>m;

    for (long long i=1;i<=m;i++)
        {long long x,y,c;
        fi>>x>>y>>c;
        G[x].push_back({y,c});}

    for (long long i=2;i<=n;i++)
        d[i]=INF;
}

void dijkstra()
{
    long long nod,cst;
    priority_queue<pair<long long,
    long long>, vector <pair <long long,long long> >, greater < pair <long long,long long> > > pq;

    pq.push({0,1});

    while(!pq.empty())
    {
        nod=pq.top().second;
        cst=pq.top().first;
        pq.pop();

        if(d[nod]!=cst) continue;

        for(long long i=0;i<G[nod].size();i++)
            if(cst+G[nod][i].second<d[G[nod][i].first])
                {d[G[nod][i].first]=cst+G[nod][i].second;
                pq.push({d[G[nod][i].first],G[nod][i].first});}



    }
}

int main()
{
    dostuff();

    dijkstra();

    for(long long i=2;i<=n;i++)
        fo<<d[i]<<" ";

    return 0;
}