#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define Nmax 50000+5
#define INF 0x3f3f3f3f
using namespace std;

int n,m;
vector < pair<int, int> > L[Nmax];
int d[Nmax];


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

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

void initializare_d()
{
    d[1]=0;
    for (int i=2; i<=n; i++)
        d[i]=INF;
}

void Dijkstra()
{
    minHeap.push(make_pair(0, 1));
    while ( !minHeap.empty() )
    {
        int x=minHeap.top().second;
        minHeap.pop();
        for (int i=0; i<L[x].size(); i++)
        {
            int v=L[x][i].second;
            int c=L[x][i].first;
            if (d[v] > d[x]+c)
            {
                d[v]=d[x]+c;
                minHeap.push(make_pair(d[v], v));
            }
        }
    }
}

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

void afisare_graf()
{
    for (int i=1; i<=n; i++)
        if (L[i].size())
        {
            printf("%d ",i);
            for (int j=0; j<L[i].size(); j++)
                printf("%d ",L[i][j].second);
            printf("\n");
        }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    initializare_d();
    Dijkstra();
    ///afisare_graf();
    afisare();
    return 0;
}