#include <cstdio>
#include <vector>
#include <queue>
#define N 50005
#define inf (1<<29)
using namespace std;
struct muchie{
             int nod,cost;
             };
vector <muchie> g[N];
int n,dist[N];
bool viz[N];
void read()
{
int m,x;
muchie p;
freopen("dijkstra.in","r",stdin);
scanf("%d%d",&n,&m);
while (m--)
    {
    scanf("%d%d%d",&x,&p.nod,&p.cost);
    g[x].push_back(p);
    }
}
void solve()
{
int i,nod;
vector <muchie>::iterator it;
queue <int> q;
for (i=2;i<=n;i++) dist[i]=inf;
q.push(1);
while (!q.empty())
   {
   nod=q.front();q.pop();
   viz[nod]=0;
   for (it=g[nod].begin();it!=g[nod].end();++it)
   if (dist[it->nod]>dist[nod]+it->cost) {
                                  dist[it->nod]=dist[nod]+it->cost;
                                  if (!viz[it->nod])
                                      {
                                       q.push(it->nod);
                                       viz[it->nod]=1;
                                      }
                                 }
   }
}
void write()
{
int i;
freopen("dijkstra.out","w",stdout);
for (i=2;i<=n;++i)
if (dist[i]==inf) printf("0 ");
else printf("%d ",dist[i]);
}
int main()
{
read();
solve();
write();
return 0;
}