#include<queue>
#include<iostream>
#include<vector>
#define INF 1e9
#define MAX 10
using namespace std;
int dist[7]
vector<pair<int, int>> graph[10];
vector<int> Dijkstra(int start) {
priority_queue<pair<int, int>> pq;
dist[start] = 0;
pq.push({ -dist[start], start });
while (!pq.empty()) {
int here = pq.top().second;
int heredist = -pq.top().first;
int size = graph[here].size();
pq.pop();
if (heredist > dist[here])
continue;
for (int i = 0; i < size; i++) {
int next = graph[here][i].first;
int nextdist = heredist + graph[here][i].second;
if (nextdist < dist[next]) {
dist[next] = nextdist;
pq.push({ -nextdist, next });
}
}
}
return dist;
}
int main() {
vector<int> res;
graph.resize(7);
graph[1].push_back(make_pair(2, 8));
graph[1].push_back(make_pair(3, 1));
graph[1].push_back(make_pair(4, 2));
graph[3].push_back(make_pair(2, 5));
graph[3].push_back(make_pair(4, 2));
graph[4].push_back(make_pair(5, 3));
graph[4].push_back(make_pair(6, 5));
graph[5].push_back(make_pair(6, 1));
graph[6].push_back(make_pair(1, 5));
res = Dijkstra(1);
for (int i = 1; i < res.size(); i++)
cout << res[i] << " ";
}