#include <bits/stdc++.h>

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

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

void Dijkstra();
void Read();

struct Pct{
int y;
int Cost;
};

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

struct Compare
{
    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 = 0; repeat <= n; ++repeat)
    {
         cst[repeat] = INF;
         use[repeat] = 0;
    }
}

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

         for (auto k : G[x])
         {
              int y = k.y;
              int crtcst = k.Cost;
              if (cst[y] > cst[x] + crtcst)
              {
                  cst[y] = cst[x] + crtcst;
                  if (!use[y])
                  {
                      use[y] = 1;
                      H.push(y);
                  }
              }
         }
    }

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