#include <fstream>
#include <utility>
#include <queue>
#include <vector>

#define MAX_VERTEXES 3005
#define INFINITY 0xffffffffffffffff

using namespace std;
using ull = unsigned long long;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int, int>> graph[MAX_VERTEXES];
ull distances[MAX_VERTEXES];
bool inQueue[MAX_VERTEXES];
bool visited[MAX_VERTEXES];
int n, m;
int start = 1;

struct compare {
    bool operator()(const int& x, const int& y) {
        return distances[x] > distances[y];
    }
};

void read() {
    int x, y, c;
    fin >> n >> m;

    for (int i = 1;i <= m;i ++) {
        fin >> x >> y >> c;
        graph[x].push_back(make_pair(y, c));
    }
}

void shortestPaths() {
    priority_queue<int, vector<int>, compare> q;

    for (int i = 1;i <= n;i ++) {
        distances[i] = INFINITY;
        inQueue[i] = false;
    }

    distances[start] = 0;
    inQueue[start] = true;
    q.push(start);

    while(!q.empty()) {
        ull current = q.top();
        q.pop(); 

        for (auto vertex : graph[current]) {
            int neighbour_vertex = vertex.first;
            int cost_vertex = vertex.second;

            
            if (distances[neighbour_vertex] > distances[current] + cost_vertex) {
                distances[neighbour_vertex] = distances[current] + cost_vertex;
                
                if (!inQueue[neighbour_vertex]) {
                    q.push(neighbour_vertex);
                    inQueue[neighbour_vertex] = true;
                }
                
            }
        }
    }
}

void print() {
    for (int i = 2;i <= n;i ++) {
        if (distances[i] == INFINITY)
            fout << 0 << ' ';
        else
            fout << distances[i] << ' ';
    }
}


int main() {
   
    read();
    shortestPaths();
    print();
    
    return 0;
}