#include <iostream>
#include <queue>
#include <vector>
#include <stack>

using std::cin;
using std::cout;
using std::vector;
using std::stack;
using std::priority_queue;
using ull = unsigned long long;

class Dij
{
public:
	struct Edge
	{
		int ver;
		int cost;

		Edge(int v, int w) :ver(v), cost(w) {}
	};
	struct Vert
	{
		int ver;
		int dist[1010];
		vector<Edge*> next;

		bool operator<(const Vert& rhs) const { return dist > rhs.dist; }
		bool operator>(const Vert& rhs) const { return dist < rhs.dist; }
	} Head[1010];
	int vis[1010];

	const int max = 1 << 20;

	ull Dijskra(int n);
};

ull Dij::Dijskra(int n)
{
	for (int i = 1; i <= n; i++)
	{
		priority_queue<Vert*> Q;
		for (int j = 1; j <= n; j++)
		{
			vis[j] = 0;
			Head[j].dist[i] = max;
		}
		Head[i].dist[i] = 0;
		Q.push(&Head[i]);
		while (!Q.empty())
		{
			int u = Q.top()->ver;
			Q.pop();
			if (vis[u]) continue;
			vis[u] = 1;
			for (int k = 0; k < Head[u].next.size(); k++)
			{
				int v = Head[u].next[k]->ver;
				int w = Head[u].next[k]->cost;
				if (vis[v] == 0)
				{
					if (Head[v].dist[i] > Head[u].dist[i] + w)
					{
						Head[v].dist[i] = Head[u].dist[i] + w;
						Q.push(&Head[v]);
					}
				}
			}
		}
	}

	ull ans = 0;
	for (int i = 1; i <= n; i++)
		ans += Head[i].dist[1] + Head[1].dist[i];

	return ans;
}

Dij D;

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		D.Head[i].ver = i;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		D.Head[u].next.push_back(new Dij::Edge(v, w));
	}
	cout << D.Dijskra(n);

	return 0;
}