#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

#define INFINIT 0x3f3f3f3f
#define NMAX 50005
#define MMAX 100005
int distante[NMAX];

int Dijkstra(vector <pair<int, int> > graf[MMAX], int n, int m, int sursa) {
    queue<int> Coada;
    memset(distante, INFINIT, sizeof(distante));

    distante[sursa] = 0;
    Coada.push(sursa);

    while(!Coada.empty()) {
        int x = Coada.front();
        Coada.pop();

        for(vector<pair<int, int> >::iterator it = graf[x].begin(); it!= graf[x].end(); ++it) {
            if(distante[it->first]  > distante[x] + it->second) {
                distante[it->first] = distante[x] + it->second;
                Coada.push(it->first);
            }

        }
    }
}


int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n,m;
    vector< pair<int, int> > graf[MMAX];

    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        int a,b,c;
        scanf("%d %d %d\n", &a, &b, &c), graf[a].push_back({b,c});
    }

    Dijkstra(graf, n, m, 1);

    for(int i = 2; i <= n; i++)
        printf("%d ", distante[i] == INFINIT ? 0 : distante[i]);

    return 0;
}