#include <fstream>
#include <queue>
#define inf 2000009;
using namespace std;
ifstream d("dijkstra.in");
ofstream o("dijkstra.out");
int n,m,a,b,c,i,j,t,e[50009],ad[5000][5000],n1,n2,vec;
bool v[50009];
int main()
  {
    queue <int> q;
    d>>n>>m;
    for (i=1;i<=m;i++) {d>>a>>b>>c; ad[a][b]=c;};
    q.push(1);
    for (i=1;i<=n;i++) e[i]=inf;
    e[1]=0;
    while (!q.empty())
      {
        n1=q.front();
        q.pop();
        for (i=1;i<=n;i++)
          if ((ad[n1][i]!=0)&(!v[i]))
            if (e[i]>e[n1]+ad[n1][i])
              {e[i]=e[n1]+ad[n1][i]; q.push(i);};
        v[n1]=1;
      }
    for (i=2;i<=n;i++) o<<e[i]<<' ';
  }