#include <fstream>
#include <climits>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,x,i,a[1001][1001],tata[1001],d[1001],j,minim,p,x2,y,x1,viz[1001];

void rec (int i)
{
    if(tata[i]!=0){rec(tata[i]);
    g<<i<<" ";
    }
}


int main()
{
    f>>n>>m;
    x=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
       {

        a[i][j]=INT_MAX/2;
        a[i][i]=0;

       }


    for(i=1;i<=m;i++)
    {
        f>>x1>>x2>>y;
        a[x1][x2]=y;
    }

      for(i=1;i<=n;i++)
    {
        tata[i]=x;
        d[i]=a[x][i];
    }
    tata[x]=0;
    viz[x]=1;
    for(i=1;i<=n-1;i++)
    {
        minim=INT_MAX;
        for(j=1;j<=n;j++)
        {
            if(viz[j]==0&&d[j]<minim){minim=d[j];p=j;}
        }

     viz[p]=1;

     for(j=1;j<=n;j++)
     {
         if(viz[j]==0&&d[j]>minim+a[p][j])
         {
             d[j]=minim+a[p][j];
             tata[j]=p;
         }
     }




    }

   /* for(i=1;i<=n;i++)
        g<<d[i]<<" ";
    g<<'\n';
    for(i=1;i<=n;i++)
        g<<tata[i]<<" ";
    g<<'\n';
    */

/*    for(i=1;i<=n;i++)
    {
        g<<x<<" ";
        rec(i);
        g<<'\n';
    }
*/

for(i=2;i<=n;i++)
{
 if(d[i]<INT_MAX/2)g<<d[i]<<" ";
 else g<<0<<" ";
}
    return 0;
}