#include <cstring>
#include <iostream>
#include <utility>
#include <vector>
#define FOR_EDGE(u, i) for (int i = idx[u]; i; i = next[i])
constexpr int N = 1E5, M = 1E5;
int u[M], v[M]; int a[M];
int deg[N + 1];
int idx[N + 1];
int to[M]; int next[M];
int id[N + 1];
std::vector<std::pair<int, int>> C[N + 1];
int main()
{
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);
	int n, m; std::cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		std::cin >> u[i] >> v[i] >> a[i];
		++deg[u[i]];
		++deg[v[i]];
	}
	std::memset(idx + 1, -1, sizeof(*idx) * n);
	for (int i = 0; i < m; ++i)
	{
		int u = ::u[i], v = ::v[i];
		auto add_edge = [i](int u, int v) {
			to[i] = v, next[i] = idx[u];
			idx[u] = i;
		};
		if (deg[u] < deg[v] || deg[u] == deg[v] && u < v)
			add_edge(u, v);
		else
			add_edge(v, u);
	}
	for (int u = 1; u <= n; ++u)
	{
		FOR_EDGE(u, i)
			id[to[i]] = i;
		FOR_EDGE(u, i)
		{
			int v = to[i];
			FOR_EDGE(v, j)
			{
				int w = to[j];
				if (int k = id[w])
				{
					int s = a[i] + a[j] + a[k];
					C[u].emplace_back(j, s);
					C[v].emplace_back(k, s);
					C[w].emplace_back(i, s);
				}
			}
		}
		FOR_EDGE(u, i)
			id[to[i]] = 0;
	}
}