#include <bits/stdc++.h>
#define N 50003
#define oo 20000003
using namespace std;

int n,m;
vector <pair <int,int> > L[N];
bitset <N> viz;
int d[N];       /// dmin,nod
priority_queue <pair<int,int> > q;

void Read()
{
    int i,x,y,cost;

    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, &cost);
        L[x].push_back({y,cost});
    }
}

void Dijkstra()
{
    int i,k;

    for (i = 1; i <= n; i++)
        d[i] = oo;

    d[1] = 0;
    /// adaug in coada perechea (0,1);
    q.push({0,1});
    while(!q.empty())
    {
        k = q.top().second; /// scot nodul
        q.pop();

        if (viz[k] == 0)
        {
            viz[k] = 1;
            for (auto w : L[k])
                if (d[w.first] > d[k] + w.second)
                {
                    d[w.first] = d[k] + w.second;
                    q.push({-d[w.first],w.first});
                }
        }
    }
}

void Afis()
{
    int i;

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

int main()
{
    Read();
    Dijkstra();
    Afis();

    return 0;
}