#include<fstream>
#include<vector>
#include<queue>
#define NMAX 50005
#define INF 999999
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

long N,M,d[NMAX];

struct muchie{ long x,cst;};
vector<muchie>L[NMAX];

struct comp{
bool operator() (long i,long j)
{
   return d[i]>d[j];
}
};

priority_queue<long,vector<long>,comp> q;

void drum()
{
    d[1]=0;
    q.push(1);
    long k;

    while(!q.empty())
          {
                k=q.top();
                q.pop();
                for (unsigned int i=0;i<L[k].size();i++)
                    if (d[L[k][i].x]>d[k]+L[k][i].cst)
                      {d[L[k][i].x]=d[k]+L[k][i].cst;
                      q.push(L[k][i].x);}


          }

}


int main()
{
    f>>N>>M;
    for (long i=1;i<=M;i++)
    {
        int nod;
        muchie y;

        f>>nod>>y.x>>y.cst;
        L[nod].push_back(y);
    }

    for (int i=1;i<=N;i++)
    d[i]=INF;
    drum();

    for (long i=2;i<=N;i++)
    g<<d[i]<<" ";

return 0;
}