#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

#define NMAX 50005
#define INF 10000000000ll
using namespace std;

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

void Dijkstra();
void Read();

struct Pct{
int y;
int c;
} p;

vector <Pct> G[NMAX];
int n, m, ok;
bool use[NMAX], sub[NMAX];
long long int cst[NMAX];

class Compare
{
    public:
    bool operator() (int a, int b)
    {
        ///min-heap
        return cst[a] > cst[b];
    }
};

priority_queue <int, vector <int>, Compare> H;

int main()
{
    Read();
    Dijkstra();
    return 0;
}

void Read()
{
    in >> n >> m;
    ok = 1;
    Pct p; int x;
    while (m)
    {
        in >> x >> p.y >> p.c;
        G[x].push_back(p);
        --m;
    }

    for (int repeat = 1; repeat <= n; ++repeat) cst[repeat] = INF;
    cst[ok] = 0;
}

void Dijkstra()
{
    H.push(ok);
    for (int repeat = 1; repeat <= n; ++repeat)
    {
         int x = -1;
         bool found = 0;
         while (!H.empty())
         {
             x = H.top(); H.pop();
             if (!use[x])
             {
                 found = 1;
                 break;
             }
         }

         if (!found)
         {
            repeat = n + 1;
            break;
         }

         use[x] = 1;
         for (int k = 0; k < G[x].size(); ++k)
         {
              int y = G[x][k].y;
              long long int crtcst = G[x][k].c;
              if (cst[y] > cst[x] + crtcst)
              {
                  cst[y] = cst[x] + crtcst;
                  sub[y] = x;
                  if (!use[y])
                      H.push(y);
              }
         }
    }

    for (int k = 1; k <= n; ++k)
         if (cst[k] == INF)
             cst[k] = 0;

    for (int k = 2; k <= n; ++k)
         out << cst[k] << " ";
}