#include <bits/stdc++.h>
#define mp std::make_pair
#define index second
#define cost first
#define dimn 50005
using nod = std::pair <int, int>;
const int inf = INT_MAX;

std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");

int N;
std::list <nod> vec[dimn];
int dist[dimn];
bool seen[dimn];

class custom_greater {
    public:
        bool operator() (int x, int y) {
            return dist[x] > dist[y];
        }
};

void dijkstra(int src=1) {
    for (int i=0; i<=N; i++) dist[i] = inf;

    std::priority_queue <int, std::vector <int>, custom_greater> pq;
    pq.push(src); dist[src] = 0;
    int pres;

    while(!pq.empty()) {
        pres = pq.top();
        pq.pop();
        seen[pres] = 0;

        for (auto vecin:vec[pres]) {
            if(dist[vecin.index] > dist[pres] + vecin.cost) {
                dist[vecin.index] = dist[pres] + vecin.cost;
                if(!seen[vecin.index])
                    pq.push(vecin.index), seen[vecin.index] = 1;
                else;
            }
        }
    }
}

void citire() {
    f >> N;
    int m; f >> m;
    for (int i=0, c, y, x; i<m; i++) {
        f >> x >> y >> c;
        vec[x].push_back(mp(c, y));
    }
}
void rezolvare() {
    dijkstra();
    for (int i=2; i<=N; i++)
        if(dist[i] == inf)
            g << 0 << " " ;
        else
            g << dist[i] << " " ;
}

int main()
{
    citire();
    rezolvare();

    return 0;
}