#include <cstdio>
#include <set>
#define DIM 50005
#define mp make_pair
using namespace std;
const int INF = 1<<30;
struct nod
{
    int x, cost;
    nod *next;
};
nod *G[DIM];

int n, m, d[DIM], H[DIM], poz[DIM], lh;
 set< pair<int, int>  > S;

void afis_heap()
{
    if (lh == 0)
    {
        printf ("VID\n");
        return ;
    }

    for (int i = 1; i <= lh; ++i)
        printf ("%3d ", H[i]);

    printf ("\n");
    for (int i = 1; i <= lh; ++i)
        printf ("%3d ", i);

    printf ("\n||-----------||\n");
}

void addMuchie(int i, int j, int cost)
{
    nod *p = new nod;
    p->x = j;
    p->cost = cost;
    p->next = G[i];
    G[i] = p;
}

void swap(int &a, int &b)
{
    int aux = a;
    a = b;
    b = aux;
}

void sterge(int i)
{

    H[i] = H[lh--];
    int k;
    while ((i<<1) <= lh)
    {
        k = i<<1;
        if (d[H[k]] > d[H[k+1]] && k+1 <= lh)
            ++k;

        if (d[H[i]] > d[H[k]])
        {
            poz[H[i]] = k;
            poz[H[k]] = i;
            swap(H[i], H[k]);
            i = k;
        }
        else
            return;

    }
}

void in_sus (int i)
{

    int k  ;

    while ((i>>1) >= 1)
    {
        k = (i>>2);

        if (d[H[i]] < d[H[k]])
        {
            poz[H[i]] = k;
            poz[H[k]] = i;
            swap(H[i], H[k]);
            i = k;
        }
        else
                return;
    }

}


void dijkstra()
{
 //  S.insert(mp(0, 1));
   lh = 0;
   H[++lh] = 1;
    poz[1] = 1;
   d[1] = 0;
   int i;
   while (lh > 0)
   {
//      val = (*S.begin()).first;
//      i = (*S.begin()).second;
//      S.erase(*S.begin());
      i = H[1];

      sterge(1);
   //   afis_heap();
      for (nod *p = G[i]; p; p = p -> next)
      {

            if (d[p->x] > d[i] + p->cost)
            {
                d[p->x] = d[i] + p->cost; //S.insert(mp(d[p->x], p->x));

                if (poz[p->x] != -1)
                   in_sus(poz[p->x]);
                else
                {
                     H[++lh] = p->x;
                     poz[p->x] = lh;
                     in_sus(lh);
                }
  //              afis_heap();
            }
      }
   }
}



int main()
{
    FILE *f = fopen("dijkstra.in", "r");
    fscanf(f, "%d%d", &n, &m);
    for (int i = 2; i <= n; ++i)
        d[i] = H[i] = INF, poz[i] = -1;

    for (int x, y, c; m; --m)
    {
        fscanf(f, "%d%d%d", &x, &y, &c);
        addMuchie(x, y, c);


    }
    fclose(f);

    dijkstra();
    f = fopen("dijkstra.out", "w");
    for (int i = 2; i <= n; ++i)
        fprintf(f, "%d ", d[i] == INF ? 0 : d[i]);
    fclose(f);

    return 0;
}