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

#define NMAX 50005
#define INF 1000000004
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];
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 = 0; repeat <= n; ++repeat) cst[repeat] = INF;
    cst[ok] = 0;
}

void Dijkstra()
{
    H.push(ok);
    while (!H.empty())
    {
         int x = H.top();
         H.pop();
         if (use[x])
             continue;
         use[x] = 1;

         for (int k = 0; k < G[x].size(); ++k)
         {
              int y = G[x][k].y;
              int crtcst = G[x][k].c;
              if (cst[y] > cst[x] + crtcst)
              {
                  cst[y] = cst[x] + crtcst;
                  ///sub[y] = x;
                  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] << " ";
}