#include <iostream>
#include <fstream>
using namespace std;
#define inf 9999999
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct edge
{
    int u,v,w;
};
void belman(int src)
{
    int m,n,i,j;
    f>>n>>m;
    int d[n];
    edge e[m];
    for(i=1; i<=m; i++)
        f>>e[i].u>>e[i].v>>e[i].w;
    for(i=1; i<=n; i++)
        d[i]=inf;
    d[src]=0;
    for(i=1; i<n; i++)
        for(j=1; j<=m; j++)
            if(d[e[j].u]+e[j].w<d[e[j].v])
                d[e[j].v]=d[e[j].u] + e[j].w;
    for(i=2; i<=n; i++)
        g << d[i] << " ";
}
int main()
{
    belman(1);
    return 0;
}