#include <fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int a[100][100],d[50001],viz[50001],n,m,i ,min1,nod,j,x,y,c;
int main()
{f>>n>>m;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
{if(i!=j)a[i][j]=1001;

}
for(i=1;i<=m;i++)
{f>>x>>y>>c;
   a[x][y]=c;
}
for(i=1;i<=n;i++)
{d[i]=a[1][i];
}
viz[1]=1;
for(i=1;i<=n-1;i++)
{min1=999999;
   for(j=2;j<=n;j++)
    if(d[j]<min1&&viz[j]==0){min1=d[j];nod=j;}
viz[nod]=1;
  for(j=2;j<=n;j++)
  {if(viz[j]==0&&d[j]>d[nod]+a[nod][j])d[j]=d[nod]+a[nod][j];
  }
}
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    return 0;
}