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

vector <pair <int, int> > Graf[Nmax];
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > C;

int N,M,Cost[Nmax];

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);
        Graf[x].push_back(make_pair(c,y));
    }
    for(int i=2;i<=N;++i)
        Cost[i]=INF;
    Cost[1]=0;
}

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



int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    Citire();
    Rezolvare();
    for(int i=2;i<=N;++i)
        printf("%d ",Cost[i]);
    return 0;
}