#include <fstream>
#include <vector>
#define inf 100000010

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int n, m;
long heap[50010], l, d[50010], poz[50010];

vector < pair<int, int> > c[50010];

void sift (int pos) {
    int son = 0;
    do {
        son = 0;
        if (2 * pos <= l) {
            if ( d[heap[pos] ] > d[heap[2*pos] ] ) son = 2*pos;

            if ( 2*pos+1 <= l ) {
                if ( d[heap[2*pos+1] ] < d[heap[pos] ] && d[heap[2*pos+1]] < d[ heap[2*pos] ])
                    son = 2*pos+1;
            }
        }

        if (son) {
            swap (heap[pos], heap[son]);
            swap (poz[ heap[pos] ], poz[ heap[son] ]);
            pos = son;
        }

    } while (son);
}

void percolate (int pos) {
    while (pos > 1 && d[ heap[pos] ] < d[ heap[pos/2] ]) {
        swap (heap[pos], heap[pos/2]);
        swap (poz[ heap[pos] ], poz[ heap[pos/2] ]);
        pos /= 2;
    }
}

void dijkstra () {
    heap[++l] = 1;
    poz[1] = 1;
    while (l > 0) {
        int nod_curent = heap[1];

        for (unsigned int i = 0; i < c[nod_curent].size(); i++) {
            long cost = d[nod_curent] + c[nod_curent][i].second;
            int node = c[nod_curent][i].first;

            if (cost < d[ node ]) {
                d[ node ] = cost;

                if ( poz[ node ] == -1) {
                    heap[++l] = node;
                    poz[ node ] = l;
                    percolate (l);
                }
                else {
                    if ( poz[node] > 1 && d[ heap[ poz[node] ] ] < d[heap[ poz[node]/2 ] ])
                        percolate( poz[node] );
                    else sift( poz[node] );
                }
            }
        }

        swap (heap[1], heap[l]);
        l--;
        if (l > 1)
            sift(1);
    }
}

int main()
{
    int i, x, y, z;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y >> z;
        c[x].push_back( make_pair(y, z) );
    }
    for (i = 2; i <= n; i++) {
        d[i] = inf;
        poz[i] = -1;
    }

    dijkstra();

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