#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 2147000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <int> v[50005],c[50005];

int n,m,cmin[50005],use[50005];

queue <int> q;

void BFord()
{ int i,nod,nod2;
   cmin[1]=0; q.push(1);
   for(i=2;i<=n;i++)
    cmin[i]=inf;
   while(!q.empty())
   { nod=q.front(); q.pop();
       for(i=0;i<v[nod].size();i++)
        if (cmin[nod]+c[nod][i]<cmin[v[nod][i]])
        { q.push(v[nod][i]);
          cmin[v[nod][i]]=cmin[nod]+c[nod][i];
        }
   }
}
int main()
{ int i,x,y,cost;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y>>cost;
       v[x].push_back(y);
       c[x].push_back(cost);
    }

   BFord();
   for(i=2;i<=n;i++)
    if (cmin[i]==inf) g<<"0 ";
    else g<<cmin[i]<<" ";
    return 0;
}