#include <fstream>
#define INF 9999999
using namespace std;

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

int n,m,x,y,c,d[50005],G[5005][5005],t[50005],i,j;
bool sel[50005];

void dijkstra ()
{
    int i,j,mi,nod;
    bool ok=true;

    for (i=1;i<=n;i++) d[i]=INF,sel[i]=false,t[i]=0;
    d[1]=0;
    nod=0;
    for (i=1; i<=n && ok; i++)
    {
        mi=INF;

        for (j=1;j<=n;j++)
            if (d[j]<mi && !sel[j])
            {
                nod=j;
                mi=d[j];
            }
        if (mi==INF) ok=false;
        else
        {
          sel[nod]=true;
          for (j=1;j<=n;j++)
            if (d[j]>d[nod]+G[nod][j] && !sel[j])
            {
                d[j]=d[nod]+G[nod][j];
                t[j]=nod;
            }
        }
    }
}
int main ()
{
    f>>n>>m;

    for (i=1;i<=n;i++){
      G[i][i]=0;
      for (j=1;j<=n;j++) G[i][j]=INF;
    }
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        G[x][y]=c;
    }

dijkstra();

for (i=2;i<=n;i++) if (d[i]!=INF) g<<d[i]<<' '; else g<<"0 ";

return 0;
}