#include <fstream>

using namespace std;

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

const int MAX_N = 50000, MAX_M = 250000, INF = 250000000;

//Graph variables
int lst[MAX_N+1], urm[MAX_M+1], vf[MAX_M+1], wght[MAX_M+1];
int nrGraph;

//Heap variables
int h[MAX_N+1];
int nrHeap;

//Dijkstra variables
int distTo[MAX_N+1];
bool visited[MAX_N+1];
int poz[MAX_N+1];

//Problem variables
int n, m;

void addEdge(int x, int y, int c)
{
    nrGraph++;
    vf[nrGraph] = y;
    wght[nrGraph] = c;
    urm[nrGraph] = lst[x];
    lst[x] = nrGraph;
}

void change(int p1, int p2)
{
    int aux = h[p2];
    h[p2] = h[p1];
    h[p1] = aux;
}

int upHeap(int p)
{
    while(p != 1 && distTo[h[p]] < distTo[h[p/2]])
    {
        change(p, p/2);
        p /= 2;
    }
    return p;
}

int downHeap(int p)
{
    int fs = 2*p, fd = 2*p+1, bun = p;
    if(fs <= nrHeap && distTo[h[fs]] < distTo[h[bun]])
        bun = fs;
    if(fd <= nrHeap && distTo[h[fd]] < distTo[h[bun]])
        bun = fd;
    if(bun != p)
    {
        change(p, bun);
        bun = downHeap(bun);
    }
    return bun;
}

void push(int index)
{
    h[++nrHeap] = index;
    poz[index] = nrHeap;
    poz[index] = upHeap(nrHeap);
}

void pop(int p)
{
    if(h[p] != 0)
    {
        change(p, nrHeap--);
        poz[h[p]] = upHeap(p);
        poz[h[p]] = downHeap(p);
    }
}

int top()
{
    return h[1];
}

bool isEmpty()
{
    return (nrHeap == 0);
}

void dijkstra()
{
    for(int i = 2; i <= n; i++)
    {
        distTo[i] = INF;
    }
    distTo[1] = 0;
    push(1);
    while(!isEmpty())
    {
        int v = top();
        pop(poz[v]);
        poz[v] = 0;
        int p = lst[v];
        while(p != 0)
        {
            if(distTo[vf[p]] > distTo[v] + wght[p])
            {
                distTo[vf[p]] = distTo[v] + wght[p];
                if(poz[vf[p]] != 0)
                {
                    poz[vf[p]] = upHeap(poz[vf[p]]);
                } else
                {
                    push(vf[p]);
                }
            }
            p = urm[p];
        }
    }
}

int main()
{
    in >> n >> m;
    int x, y, w;
    for(int i = 1; i <= m; i++)
    {
        in >> x >> y >> w;
        addEdge(x,y,w);
    }
    dijkstra();
    for(int i = 2; i <= n; i++)
    {
        out << distTo[i] << " ";
    }
    return 0;
}