#include <iostream>
#include <fstream>
using namespace std;
int c[23001][23001],d[23001],t[23001],viz[23001];
const int inf=30001;
int n,m,x,y,i,j,cost;
ofstream g("dijkstra.out");
void citire()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
      for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
                c[i][j]=inf;

    for(int i=1;i<=m;i++)
        {f>>x>>y>>cost;
        c[x][y]=cost;}
}
void dij(int s)
{
    int ok=1,mini,k;
    for(i=1;i<=n;i++)
    {
        d[i]=c[s][i];
        if(i!=s && d[i]!=inf)
            t[i]=s;
        else
            t[i]=0;
        viz[i]=0;
    }
    viz[s]=1;
    while(ok==1)
    {
        mini=inf;
        for(i=1;i<=n;i++)
            if(viz[i]==0 && d[i]<mini)
        {
            mini=d[i];
            k=i;
        }
        if(mini==inf)
            ok=0;
        else
        {
            viz[k]=1;
            for(i=1;i<=n;i++)
                if(viz[i]==0 && d[i]>d[k]+c[k][i])
            {
                d[i]=d[k]+c[k][i];
                t[i]=k;
            }
        }
    }
}

int main()
{     citire();
      dij(1);
      for(i=2;i<=n;i++)
        g<<d[i]<<" ";
}