#include <iostream>
#include <fstream>
#include <vector>
#include <utility>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int distanta[50005];
vector <pair <int, int> > G[50005];

int main()
{
    int n,m,i,j,k,a,b,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
    }
    for(i=1;i<=n;i++)
        distanta[i]=1<<30;
    distanta[1]=0;
    for(i=1;i<=n-1;i++)
        for(j=1;j<=n;j++)
            for(k=0;k<G[j].size();k++)
                if(distanta[j]+G[j][k].second<distanta[G[j][k].first])
                    distanta[G[j][k].first]=distanta[j]+G[j][k].second;
    for(i=2;i<=n;i++)
        g<<distanta[i]<<' ';
    return 0;
}