#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2559"
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <vector>
#include "Mylib/DataStructure/Heap/binomial_heap.cpp"
#include "Mylib/Graph/MinimumSpanningTree/prim.cpp"
#include "Mylib/Graph/Template/graph.cpp"
#include "Mylib/Misc/merge_technique.cpp"
#include "Mylib/Utils/fix_point.cpp"
namespace hl = haar_lib;
int main() {
int n, m;
std::cin >> n >> m;
hl::graph<int64_t> g(n);
g.read<1, false>(m);
std::map<std::pair<int, int>, int> index;
for (auto &a : g) {
for (auto &e : a) index[{e.from, e.to}] = e.index;
}
auto res = hl::prim(g);
std::vector<int64_t> ans(m, -1);
if ((int) res.size() == n - 1) {
int64_t s = 0;
hl::tree<int64_t> tree(n);
for (auto &e : res) {
s += e.cost;
tree[e.from].push_back(e);
}
ans.assign(m, s);
std::vector<hl::binomial_heap<std::tuple<int64_t, int, int>, std::greater<>>> heaps(n);
std::vector<std::set<int>> sub(n);
hl::make_fix_point(
[&](auto &&f, int cur, int par, int64_t cost) -> void {
for (auto &e : g[cur]) {
heaps[cur].push({e.cost, e.from, e.to});
}
sub[cur].insert(cur);
for (auto &e : tree[cur]) {
if (e.to == par) continue;
f(e.to, cur, e.cost);
heaps[cur].meld(heaps[e.to]);
hl::merge_technique(sub[cur], sub[cur], sub[e.to]);
}
if (par != -1) {
while (not heaps[cur].empty()) {
auto [c, i, j] = heaps[cur].top();
if ((sub[cur].find(i) != sub[cur].end() and sub[cur].find(j) != sub[cur].end()) or
(i == cur and j == par) or (i == par and j == cur)) {
heaps[cur].pop();
} else {
break;
}
}
if (not heaps[cur].empty()) {
ans[index[{cur, par}]] = s - cost + std::get<0>(heaps[cur].top());
} else {
ans[index[{cur, par}]] = -1;
}
}
})(0, -1, 0);
}
for (auto x : ans) {
std::cout << x << std::endl;
}
return 0;
}
#line 1 "test/aoj/2559/main.binomial_heap.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2559"
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <vector>
#line 2 "Mylib/DataStructure/Heap/binomial_heap.cpp"
#include <array>
#include <cassert>
#include <functional>
#line 6 "Mylib/DataStructure/Heap/binomial_heap.cpp"
namespace haar_lib {
template <typename T, typename Compare = std::less<T>>
class binomial_heap {
public:
using value_type = T;
private:
struct node {
T value;
std::vector<node *> children;
node(T value) : value(value) {}
};
constexpr static int MAX = 31;
std::array<node *, MAX> roots_;
Compare compare_;
int top_index_ = -1;
int heap_size_ = 0;
node *merge(node *a, node *b) {
if (compare_(a->value, b->value)) std::swap(a, b);
a->children.push_back(b);
return a;
}
template <typename Container>
void meld(Container c) {
node *s = nullptr;
for (int i = 0; i < MAX; ++i) {
std::vector<node *> temp;
if (s) {
temp.push_back(s);
s = nullptr;
}
if (roots_[i]) {
temp.push_back(roots_[i]);
roots_[i] = nullptr;
}
if (i < (int) c.size() and c[i]) {
temp.push_back(c[i]);
c[i] = nullptr;
}
switch (temp.size()) {
case 1: roots_[i] = temp[0]; break;
case 2: s = merge(temp[0], temp[1]); break;
case 3:
roots_[i] = temp[0];
s = merge(temp[1], temp[2]);
break;
}
}
top_index_ = -1;
for (int i = 0; i < MAX; ++i) {
if (roots_[i]) {
if (top_index_ == -1 or compare_(roots_[top_index_]->value, roots_[i]->value)) {
top_index_ = i;
}
}
}
}
public:
binomial_heap() {
roots_.fill(nullptr);
compare_ = Compare();
}
int size() const {
return heap_size_;
}
bool empty() const {
return heap_size_ == 0;
}
void push(const T &value) {
heap_size_ += 1;
node *t = new node(value);
meld(std::vector<node *>({t}));
}
const T &top() const {
return roots_[top_index_]->value;
}
void pop() {
heap_size_ -= 1;
node *t = roots_[top_index_];
roots_[top_index_] = nullptr;
meld(t->children);
delete t;
}
void meld(binomial_heap &rhs) {
heap_size_ += rhs.heap_size_;
meld(rhs.roots_);
rhs.roots_.fill(nullptr);
}
};
} // namespace haar_lib
#line 2 "Mylib/Graph/MinimumSpanningTree/prim.cpp"
#include <queue>
#line 4 "Mylib/Graph/Template/graph.cpp"
namespace haar_lib {
template <typename T>
struct edge {
int from, to;
T cost;
int index = -1;
edge() {}
edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
edge(int from, int to, T cost, int index) : from(from), to(to), cost(cost), index(index) {}
};
template <typename T>
struct graph {
using weight_type = T;
using edge_type = edge<T>;
std::vector<std::vector<edge<T>>> data;
auto& operator[](size_t i) { return data[i]; }
const auto& operator[](size_t i) const { return data[i]; }
auto begin() const { return data.begin(); }
auto end() const { return data.end(); }
graph() {}
graph(int N) : data(N) {}
bool empty() const { return data.empty(); }
int size() const { return data.size(); }
void add_edge(int i, int j, T w, int index = -1) {
data[i].emplace_back(i, j, w, index);
}
void add_undirected(int i, int j, T w, int index = -1) {
add_edge(i, j, w, index);
add_edge(j, i, w, index);
}
template <size_t I, bool DIRECTED = true, bool WEIGHTED = true>
void read(int M) {
for (int i = 0; i < M; ++i) {
int u, v;
std::cin >> u >> v;
u -= I;
v -= I;
T w = 1;
if (WEIGHTED) std::cin >> w;
if (DIRECTED)
add_edge(u, v, w, i);
else
add_undirected(u, v, w, i);
}
}
};
template <typename T>
using tree = graph<T>;
} // namespace haar_lib
#line 5 "Mylib/Graph/MinimumSpanningTree/prim.cpp"
namespace haar_lib {
template <typename T>
std::vector<edge<T>> prim(const graph<T> &graph) {
const int n = graph.size();
std::vector<bool> visit(n, false);
std::vector<edge<T>> ret;
auto cmp = [](const auto &a, const auto &b) { return a.cost > b.cost; };
std::priority_queue<edge<T>, std::vector<edge<T>>, decltype(cmp)> pq(cmp);
visit[0] = true;
for (auto &e : graph[0]) pq.push(e);
while (not pq.empty()) {
auto t = pq.top();
pq.pop();
if (visit[t.from] == visit[t.to]) continue;
int i = visit[t.from] ? t.to : t.from;
for (auto &e : graph[i]) {
pq.push(e);
}
visit[i] = true;
ret.push_back(t);
}
return ret;
}
} // namespace haar_lib
#line 3 "Mylib/Misc/merge_technique.cpp"
#include <utility>
namespace haar_lib {
template <typename T>
void merge_technique(std::set<T> &res, std::set<T> &a, std::set<T> &b) {
if (a.size() > b.size()) {
a.insert(b.begin(), b.end());
std::swap(res, a);
} else {
b.insert(a.begin(), a.end());
std::swap(res, b);
}
}
} // namespace haar_lib
#line 3 "Mylib/Utils/fix_point.cpp"
namespace haar_lib {
template <typename F>
struct fix_point : F {
explicit constexpr fix_point(F &&f) noexcept : F(std::forward<F>(f)) {}
template <typename... Args>
constexpr auto operator()(Args &&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <typename F>
inline constexpr auto make_fix_point(F &&f) {
return fix_point<F>(std::forward<F>(f));
}
template <typename F>
inline constexpr auto make_fix_point(F &f) {
return fix_point<F>(std::forward<F>(f));
}
} // namespace haar_lib
#line 13 "test/aoj/2559/main.binomial_heap.test.cpp"
namespace hl = haar_lib;
int main() {
int n, m;
std::cin >> n >> m;
hl::graph<int64_t> g(n);
g.read<1, false>(m);
std::map<std::pair<int, int>, int> index;
for (auto &a : g) {
for (auto &e : a) index[{e.from, e.to}] = e.index;
}
auto res = hl::prim(g);
std::vector<int64_t> ans(m, -1);
if ((int) res.size() == n - 1) {
int64_t s = 0;
hl::tree<int64_t> tree(n);
for (auto &e : res) {
s += e.cost;
tree[e.from].push_back(e);
}
ans.assign(m, s);
std::vector<hl::binomial_heap<std::tuple<int64_t, int, int>, std::greater<>>> heaps(n);
std::vector<std::set<int>> sub(n);
hl::make_fix_point(
[&](auto &&f, int cur, int par, int64_t cost) -> void {
for (auto &e : g[cur]) {
heaps[cur].push({e.cost, e.from, e.to});
}
sub[cur].insert(cur);
for (auto &e : tree[cur]) {
if (e.to == par) continue;
f(e.to, cur, e.cost);
heaps[cur].meld(heaps[e.to]);
hl::merge_technique(sub[cur], sub[cur], sub[e.to]);
}
if (par != -1) {
while (not heaps[cur].empty()) {
auto [c, i, j] = heaps[cur].top();
if ((sub[cur].find(i) != sub[cur].end() and sub[cur].find(j) != sub[cur].end()) or
(i == cur and j == par) or (i == par and j == cur)) {
heaps[cur].pop();
} else {
break;
}
}
if (not heaps[cur].empty()) {
ans[index[{cur, par}]] = s - cost + std::get<0>(heaps[cur].top());
} else {
ans[index[{cur, par}]] = -1;
}
}
})(0, -1, 0);
}
for (auto x : ans) {
std::cout << x << std::endl;
}
return 0;
}