#include <iostream>
#include <fstream>
#include <vector>
#define INF 2147483647
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
int n,m;
vector <pair<int,int> >V[50001];
int D[50001];
int F[50001];
void Dijkastra(int nodeF)
{
    while(1)
    {
        int index=1;
        int WW=-1;
        while(index<=n && WW==-1)
        {
            if(F[index]==0 && D[index]!=INF)
            {
                WW=index;
                F[index]=1;
                continue;
            }
            index++;
        }
        if(WW==-1)
            break;
        for(int i=0;i<V[WW].size();i++)
        {
            int vecin=V[WW][i].first;
            D[vecin]=min(D[vecin],D[WW]+V[WW][i].second);
        }
    }
}
int main()
{
    fi>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,C;
        fi>>x>>y>>C;
        V[x].push_back(make_pair(y,C));
    }
    for(int i=2;i<=n;i++)
        D[i]=INF;
    F[1]=1;
    for(int i=0;i<V[1].size();i++)
    {
        int vecin=V[1][i].first;
        D[vecin]=V[1][i].second;
    }
    Dijkastra(1);
    for(int i=2;i<=n;i++)
        fo<<D[i]<<" ";
    return 0;
}