#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f
#define N 50005

using namespace std;

int n,m,d[N];

vector <pair <int,int> >G[N];

priority_queue <pair<int,int> , vector <pair<int, int> > , greater <pair <int , int> > > q;

vector<pair<int,int> >::iterator it;

void afisare()
{
    for(int i = 2; i <= n ; ++i)
    {
        if(d[i]==inf)
        {
            printf("0 ");
            continue;
        }
        printf("%d ",d[i]);
    }
}

void prelucrare()
{
    q.push(make_pair(0,1));

    d[1] = 0;

    while(!q.empty())
    {
        int tmp = q.top().second;

        if(d[tmp] < q.top().first)
        {
            q.pop();

            continue;
        }

        q.pop();

        for(it = G[tmp].begin(); it != G[tmp].end(); ++it)
        {
            int x = d[tmp] + it->first;

            if(x < d[it->second] )
            {
                q.push(make_pair(x , it->second));

                d[it->second] = x;
            }
        }
    }
}

void citire()
{
    scanf("%d %d\n",&n,&m);

    for(int i = 0; i < m; ++i)
    {
        int a,b,c;
        scanf("%d %d %d\n",&a,&b,&c);

        G[a].push_back(make_pair(c,b));
    }

    for(int i = 2; i <= n; ++i)
    {
        d[i]=inf;
    }

    prelucrare();

    afisare();
}

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

    citire();

    return 0;
}