← Home
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

type Edge struct {
	u, v, w, id int
}

type pair struct {
	to, w int
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	const maxCapacity = 10 * 1024 * 1024
	buf := make([]byte, maxCapacity)
	scanner.Buffer(buf, maxCapacity)
	scanner.Split(bufio.ScanWords)

	nextInt := func() int {
		scanner.Scan()
		res := 0
		for _, v := range scanner.Bytes() {
			res = res*10 + int(v-'0')
		}
		return res
	}

	if !scanner.Scan() {
		return
	}
	n := 0
	for _, v := range scanner.Bytes() {
		n = n*10 + int(v-'0')
	}
	m := nextInt()

	edges := make([]Edge, m)
	for i := 0; i < m; i++ {
		edges[i].u = nextInt()
		edges[i].v = nextInt()
		edges[i].w = nextInt()
		edges[i].id = i
	}

	sortedEdges := make([]Edge, m)
	copy(sortedEdges, edges)
	sort.Slice(sortedEdges, func(i, j int) bool {
		return sortedEdges[i].w < sortedEdges[j].w
	})

	parent := make([]int, n+1)
	for i := 1; i <= n; i++ {
		parent[i] = i
	}

	var find func(int) int
	find = func(i int) int {
		if parent[i] == i {
			return i
		}
		parent[i] = find(parent[i])
		return parent[i]
	}

	adj := make([][]pair, n+1)
	var mstWeight int64
	inMST := make([]bool, m)

	for _, e := range sortedEdges {
		rootU := find(e.u)
		rootV := find(e.v)
		if rootU != rootV {
			parent[rootU] = rootV
			mstWeight += int64(e.w)
			inMST[e.id] = true
			adj[e.u] = append(adj[e.u], pair{e.v, e.w})
			adj[e.v] = append(adj[e.v], pair{e.u, e.w})
		}
	}

	up := make([][20]int, n+1)
	mx := make([][20]int, n+1)
	depth := make([]int, n+1)

	var dfs func(u, p, w, d int)
	dfs = func(u, p, w, d int) {
		up[u][0] = p
		mx[u][0] = w
		depth[u] = d
		for i := 1; i < 20; i++ {
			up[u][i] = up[up[u][i-1]][i-1]
			mx[u][i] = max(mx[u][i-1], mx[up[u][i-1]][i-1])
		}
		for _, edge := range adj[u] {
			if edge.to != p {
				dfs(edge.to, u, edge.w, d+1)
			}
		}
	}

	dfs(1, 1, 0, 0)

	getMax := func(u, v int) int {
		if depth[u] < depth[v] {
			u, v = v, u
		}
		res := 0
		diff := depth[u] - depth[v]
		for i := 0; i < 20; i++ {
			if (diff & (1 << i)) != 0 {
				res = max(res, mx[u][i])
				u = up[u][i]
			}
		}
		if u == v {
			return res
		}
		for i := 19; i >= 0; i-- {
			if up[u][i] != up[v][i] {
				res = max(res, max(mx[u][i], mx[v][i]))
				u = up[u][i]
				v = up[v][i]
			}
		}
		res = max(res, max(mx[u][0], mx[v][0]))
		return res
	}

	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	for i := 0; i < m; i++ {
		if inMST[i] {
			fmt.Fprintf(writer, "%d\n", mstWeight)
		} else {
			maxEdge := getMax(edges[i].u, edges[i].v)
			ans := mstWeight - int64(maxEdge) + int64(edges[i].w)
			fmt.Fprintf(writer, "%d\n", ans)
		}
	}
}