#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 2 * (10e6+10), M = 2 * (10e6+10), INF = 0x3f3f3f3f;

int h[N], e[M], w[M], nex[M], idx;

int dist[N];
bool vis[N];

int n, m;
int s=1;

void dijkstra()
{
    for (int i=0;i<N;i++)
    {
        dist[i] = INF;
    }
    dist[s] = 0;

    priority_queue<PII, vector<PII>, greater<PII> > heap;

    heap.push({0, s});

    while(heap.size())
    {
        int t = heap.top().second;

        heap.pop();

        if (vis[t]) continue;
        vis[t] = true;

        for (int i=h[t];i!=-1;i=nex[i])
        {
            int j=e[i];

            if (dist[t]+w[i] < dist[j])
            {
                dist[j] = dist[t]+w[i];
                heap.push({dist[j], j});
            }

        }


    }




}

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    nex[idx] = h[a];
    h[idx] = idx;
    idx++;

}

int main()
{
//    freopen("luogu.in", "r", stdin);
//    freopen("luogu.out", "w", stdout);

    int a, b, c;

    cin >> n >> m;

    for (int i=0;i<N;i++)
    {
        h[i] = -1;
    }

    for (int i=0;i<m;i++)
    {
        cin >> a >> b >> c;
        if (a == 1)
        {
            add(a, b, c);
        }

        else if (b == 1)
        {
            add(b+n, a+n, c);
        }

    }

    int ans = 0;

    s = 1;
    dijkstra();
    for (int i=2;i<=n;i++)
    {
        ans += dist[i];

    }


    for (int i=0;i<N;i++)
    {
        vis[i] = false;
    }


    s = 1+n;

    dijkstra();

    for (int i=1+n;i<=n+n;i++)
    {
        ans += dist[i];
    }

    cout << ans;





    return 0;
}

https://www.luogu.com.cn/problem/P1342 太晚了，大脑当机了，球调