#include <cstdio>
#include <queue>
#include <vector>
#define N 50005
#define oo 1<<31-1
using namespace std;

vector<pair<int,int>>g[N];
priority_queue < pair <int,int>,vector <pair <int,int>>, greater<pair <int,int>> >pq;
bool sel[N];
int n,m,x,y,c,i, d[N];

void Dijkstra(int st)
{
    int nod;
    int cost;

    for (i=1; i<=n; i++) d[i]=oo;
    d[st]=0;
    pq.push({st,0});

    while (!pq.empty())
    {
        nod=pq.top().first;
        cost = pq.top().second;
        pq.pop();
        if (cost<=d[nod]){
        for (auto it : g[nod] )
            if (it.second+cost<d[it.first])
            {
                d[it.first]=it.second+cost;
                pq.push ({it.first,d[it.first]});
            }

        }

    }
}

int main()
{
    freopen ("dijkstra.in", "r", stdin);
    freopen ("dijkstra.out", "w", stdout);

    scanf ("%d%d", &n, &m );
    for (i=1; i<=m ; i++)
    {
        scanf("%d%d%d", &x, &y, &c);
        g[x].push_back({y,c});
    }

    Dijkstra(1);

    for (i=2; i<=n; i++)
        if ( d[i] != oo )printf ("%d ", d[i]);
        else printf ("0 ");



    return 0;
}