#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50004
#define INF 5100000000

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");

struct muchie
{
    long long int c;
    int y;
};
vector <muchie> G[NMAX];
priority_queue <pair <long long int, int>, vector <pair <long long int, int> >, greater <pair <long long int, int> > > pq;
long long int dmin[NMAX];
bool M[NMAX];

int n, m, i, p;
muchie x;

void dijkstra();
int main()
{
 fin>>n>>m; p=1;
 while (fin>>i>>x.y>>x.c)
       G[i].push_back(x);
 dijkstra();
 for (i=2; i<=n; i++)
     if (dmin[i]==INF)
        fout<<0<<' ';
        else
        fout<<dmin[i]<<' ';
 return 0;
}

void dijkstra()
{
 int i, j;
 pair <long long int, int> a, b;
 for (i=1; i<=n; i++)
     dmin[i]=INF;
 dmin[p]=0; M[p]=1;
 for (i=0; i<G[p].size(); i++)
     {
      dmin[G[p][i].y]=G[p][i].c;
      a.first=G[p][i].c;
      a.second=G[p][i].y;
      pq.push(a);
     }
 while (!pq.empty())
       {
        do
        {
         a=pq.top();
         pq.pop();
        }
        while (M[a.second] && !pq.empty());
        if (pq.empty()) break;
        M[a.second]=1;
        for (i=0; i<G[a.second].size(); i++)
            if (dmin[G[a.second][i].y] > dmin[a.second] + G[a.second][i].c)
               {
                dmin[G[a.second][i].y]=dmin[a.second] + G[a.second][i].c;
                b.first=dmin[G[a.second][i].y];
                b.second=G[a.second][i].y;
                pq.push(b);
               }
       }
}