package main

import (
	"container/heap"
	"math"
)

type Edge struct {
	to     int32
	weight int32
}

type Item struct {
	node int32
	dist int32
}

type MinHeap []Item

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func shortestReach(n int32, edges [][]int32, s int32) []int32 {
	graph := make(map[int32][]Edge)

	// Use only smallest edge if multiple exist between two nodes
	minEdge := make(map[[2]int32]int32)
	for _, edge := range edges {
		u, v, w := edge[0], edge[1], edge[2]
		key1 := [2]int32{u, v}
		key2 := [2]int32{v, u}
		if val, ok := minEdge[key1]; !ok || w < val {
			minEdge[key1] = w
			minEdge[key2] = w
		}
	}

	// Build the graph
	for key, w := range minEdge {
		u, v := key[0], key[1]
		graph[u] = append(graph[u], Edge{to: v, weight: w})
	}

	dist := make([]int32, n+1) // 1-based indexing
	for i := int32(1); i <= n; i++ {
		dist[i] = int32(math.MaxInt32)
	}
	dist[s] = 0

	pq := &MinHeap{}
	heap.Init(pq)
	heap.Push(pq, Item{s, 0})

	visited := make([]bool, n+1)

	for pq.Len() > 0 {
		curr := heap.Pop(pq).(Item)
		u := curr.node

		if visited[u] {
			continue
		}
		visited[u] = true

		for _, e := range graph[u] {
			v := e.to
			if dist[u]+e.weight < dist[v] {
				dist[v] = dist[u] + e.weight
				heap.Push(pq, Item{v, dist[v]})
			}
		}
	}

	// Build result excluding source
	result := []int32{}
	for i := int32(1); i <= n; i++ {
		if i == s {
			continue
		}
		if dist[i] == int32(math.MaxInt32) {
			result = append(result, -1)
		} else {
			result = append(result, dist[i])
		}
	}
	return result
}

vector<pair<long, int>> shortestReach(int n, const vector<vector<pair<int, int>>>& edges, int s) {
    vector<bool> visited(n+1);
    vector<pair<long, int>> distance(n+1, {LONG_MAX, -1});
    distance[s] = {0, s};
    for (int count = 1; count <= n; ++count) {
        int shortest = -1;
        for (int i = 1; i <= n; ++i) {
            if (!visited[i] and (shortest == -1 or distance[shortest].first > distance[i].first)) shortest = i;
        }
        visited[shortest] = true;
        if (shortest == -1 or distance[shortest].first == LONG_MAX) break;
        for (auto neighbor : edges[shortest]) {
            int u = neighbor.first, W = neighbor.second;
            if (!visited[u]) distance[u].first = min(distance[u].first, distance[shortest].first + W);
        }
    }    
    return distance;
}