#include <fstream>
#include <algorithm>
#define nmax 50005
#define inf 0x3f3f3f3f

using namespace std;

struct lst
{
    int nod, weight;
    lst *next;
};

class Graph
{

public:

    lst *g[nmax];

    void AddNode(int x,int y,int w)
    {
        if (g[x] == NULL)
        {
            g[x] = new lst;
            g[x] -> nod = y;
            g[x] -> weight = w;
            g[x] -> next = NULL;
        }
        else
        {
            lst *p;
            p = g[x];
            while(p -> next != NULL)
                p = p -> next;
            p -> next = new lst;
            p -> next -> nod = y;
            p -> next -> weight = w;
            p -> next -> next = NULL;
        }
    }
};

struct heap
{
    int nod,weight;
};

class PriorityQueue
{

public:

    heap a[nmax];
    int poz[nmax],sze,lbls;

    void DecreaseValue(int x,int w)
    {
        int i = poz[x];
        a[i].weight = w;
        while(i > 1 && a[i].weight < a[i / 2].weight)
            swap(a[i],a[i / 2]);
            i = i / 2;
    }

   void heapify(int i)
   {
        int smallest = i;
        do
        {
            i = smallest;
            if(2 * i <= sze && a[2 * i].weight < a[smallest].weight)
                smallest = 2 * i;
            if(2 * i + 1 <= sze && a[2 * i + 1].weight < a[smallest].weight)
                smallest = 2 * i;
            swap(a[smallest],a[i]);
            swap(poz[a[smallest].nod],poz[a[i].nod]);
        }
        while(smallest != i);
   }

    heap Pop()
    {
        heap x = a[1];
        swap(a[1],a[sze]);
        poz[a[1].nod] = 1;
        sze--;
        heapify(1);
        return x;
    }

    void MakeHeap(int n,int d[])
    {
        sze = n;
        for(int i = 1;i <= n;i++)
        {
            a[i].nod = i;
            a[i].weight = d[i];
            poz[i] = i;
        }
        lbls = n;
    }

    bool Empty()
    {
        return (sze == 0);
    }

};

int n,m,d[nmax];
Graph grp;
PriorityQueue q;

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

void citire()
{
    int x,y,c;
    fin >> n >> m;
    for(int i = 0;i < m;i++)
    {
        fin >> x >> y >> c;
        grp.AddNode(x,y,c);
    }
    for(int i = 1; i <= n; i++)
        d[i] = inf;
}

void dijkstra()
{
    int k;
    d[1]=0;
    q.MakeHeap(n,d);
    while(!q.Empty())
    {
        k = q.Pop().nod;
        lst *p = grp.g[k];
        while(p != NULL)
        {
            if(d[p -> nod] > d[k] + p -> weight)
            {
                d[p -> nod] = d[k] + p -> weight;
                q.DecreaseValue(p -> nod,d[p -> nod]);
            }
            p = p -> next;
        }
    }
}

void afisare()
{
    for(int i = 2;i <= n;i++)
    {
        if(d[i] == inf)
            fout << 0 << " ";
        else
            fout << d[i] << " ";
    }
}

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}