#include <fstream>
#define INF 99999
using namespace std;
int d[5000],t[5000],cost[5000][5000],n,i,j,m,x,y,z,c;
bool ok,sel[5000];
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
void dijkstra (int p)
{
    int nod,j,i,mi;
    for (i=1;i<=n;i++)
        {
            d[i]=INF;
            sel[i]=false;
            t[i]=0;
        }
    d[p]=0;
    ok=true;
    for (i=1;i<=n &&ok;i++)
    {
        mi=INF;
        for (j=1;j<=n;j++)
            if (d[j]<mi && !sel[j])
                {
                    mi=d[j];
                    nod=j;
                }
        sel[nod]=true;
        if (mi==INF) ok=false;
        else {
            sel[nod]=true;
        for (j=1;j<=n;j++)
            if (d[j]>d[nod]+cost[nod][j]&&!sel[j])
                {
                    d[j]=d[nod]+cost[nod][j];
                    t[j]=nod;
                }
            }
    }
}
int main()
{
    int i;
    f>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            cost[i][j]=INF;
    for (i=1;i<=m;i++) {
        f>>x>>y>>c;
        cost[x][y]=c;
    }
    dijkstra(1);
    for (i=2;i<=n;i++)
        if  (d[i]==INF) d[i]=0;
    for (i=2;i<=n;i++)
        g<<d[i]<<' ';
    return 0;
}