#include <fstream>
#define miel 60000
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int i,j,m,n,c,d[miel],t[miel],x,y;
vector <pair<int,int> >v[miel];
queue <int> q;
void dijkstra (int sursa)
{vector <pair<int,int> > ::iterator it;
int    nod;
    d[sursa]=0;
    q.push(sursa);
    while (!q.empty())
    {nod=q.front();
    q.pop();
         for (it=v[nod].begin();it!=v[nod].end();it++)
         if (d[(*it).first]>d[nod]+(*it).second)
         {d[(*it).first]=d[nod]+(*it).second;
             q.push((*it).first);
         }
    }
}
int main()
{f>>n>>m;

for (i=1;i<=m;i++)
{f>>x>>y>>c;
v[x].push_back(make_pair(y,c));
}
for (i=1;i<=n;i++) d[i]=miel;
dijkstra(1);
for (i=2;i<=n;i++) if(d[i]!=miel)
g<<d[i]<<" ";
else g<<0<<" ";
}