#include <fstream>
#include <vector>
#include <set>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,i,nod,x,pana[50001],aprox[50001];
vector<int> V[50001],Vd[50001];
set <int> S;

void init()
{
    for (i=2;i<=n;i++)
        {pana[i] = 1000*50000+1;
         S.insert(i);}
    S.insert(1);
}
set<int>::iterator it;
int mini;
void portocala()
{
    while (!S.empty())
    {
        mini = 50000*1000+2;
        for (it = S.begin(); it!=S.end(); it++)
          if (pana[*it]<mini) {mini =pana[*it]; nod = *it;}
        S.erase(nod);
        for (size_t i = 0; i<V[nod].size(); i++)
        {
         x = pana[nod] + Vd[nod][i];
         if (x < pana[V[nod][i]])
         {
             pana[V[nod][i]] = x;
             aprox[V[nod][i]] = nod;
         }
        }
    }
}
int main()
{
    int a,b,d,i,m;
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>a>>b>>d;
        V[a].push_back(b);
        Vd[a].push_back(d);
    }
    init();
    portocala();
    for (i=2;i<=n;i++)
       if (pana[i]!=50000*1000+1) g<<pana[i]<<" "; else g<<0<<" ";
    return 0;
}