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

#define NMAX 50010
#define INF (1<<30)-1
using namespace std;

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

void Dijkstra();
void Read();

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

vector <Pct> G[NMAX];
int n, m, ok;
bool use[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.Cost;
        G[x].push_back(p);
        --m;
    }

    for (int repeat = 1; repeat <= n; ++repeat)
    {
         cst[repeat] = INF;
         use[repeat] = 0;
    }
    ok = 1;
    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)
         for (auto k : G[x])
         {
              int y = k.y;
              int crtcst = k.Cost;
              ///if (cst[y] > cst[x] + crtcst)

              cst[y] = min(cst[y], cst[x] + crtcst);
              H.push(y);
         }
    }

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