下午居然沒做出這題，我傻了。。。一直在用我不熟悉的網(wǎng)絡(luò)流在搞
網(wǎng)上也有人用最小樹形圖做
/*
    題意：給出一個(gè)有向圖，a傳到b的代價(jià)為c，同一個(gè)環(huán)內(nèi)的傳輸不用代價(jià)
           求從一個(gè)點(diǎn)傳到所有點(diǎn)的最小代價(jià)
    先強(qiáng)連通縮點(diǎn) 找到入度為0的點(diǎn)作為原點(diǎn)
    然后用spfa更新即可  更新的規(guī)則是 if(dist[v]>g[u][v])dist[v]=g[u][v]
    方正最后每個(gè)點(diǎn)都被傳到，究竟它被誰傳過來的呢？
    肯定是被花費(fèi)最小的那條邊傳過來的
    這樣子一直更新下去肯定是最優(yōu)值！
    兩種實(shí)現(xiàn)，用spfa也行   更直接的兩重循環(huán)找每個(gè)點(diǎn)的父邊中的最小值
*/
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

const int MAXN = 50000;
const int INF = 1000000000;

struct Edge
{
    int v,w;
    Edge *next;
}edge[100000*2+10],*E[MAXN+10],*_E[MAXN+10],*pE;

struct Graph
{
    vector<int>G[200];
    int SCC,n;
    int ord[MAXN+10],ID[MAXN+10];
    int g[200][200];
    int ind[200],dist[200],in[200];

    void init(int nn)
    {
        n=nn;
        memset(E,0,sizeof(E));
        memset(_E,0,sizeof(_E));
        pE=edge;
    }
    void add(int u,int v,int w)
    {
        pE->v=v;
        pE->w=w;
        pE->next=E[u];
        E[u]=pE++;

        pE->v=u;
        pE->w=w;
        pE->next=_E[v];
        _E[v]=pE++;
    }
    void dfs1(int u)
    {
        ID[u]=1;
        for(Edge *it=_E[u];it;it=it->next)
        {
            if(ID[it->v]==-1)dfs1(it->v);
        }
        ord[SCC++]=u;
    }
    void dfs2(int u)
    {
        ID[u]=SCC;
        for(Edge *it=E[u];it;it=it->next)
            if(ID[it->v]==-1)dfs2(it->v);
    }
    void kosaraju()
    {
        SCC=0;
        memset(ID,-1,sizeof(ID));
        for(int i=0;i<n;i++)
            if(ID[i]==-1)dfs1(i);
        SCC=0;
        memset(ID,-1,sizeof(ID));
        for(int i=n-1;i>=0;i--)
            if(ID[ord[i]]==-1)
            {
                dfs2(ord[i]);
                SCC++;
            }
    }
    void build()
    {
         for(int i=0;i<SCC;i++)
            for(int j=0;j<SCC;j++)
                g[i][j]=INF;
        for(int i=0;i<n;i++)
            for(Edge *it=E[i];it;it=it->next)
            {
                if(ID[i]==ID[it->v])continue;
                if(it->w<g[ID[i]][ID[it->v]])g[ID[i]][ID[it->v]]=it->w;
            }

        for(int i=0;i<SCC;i++)G[i].clear();
        memset(ind,0,sizeof(ind));
        for(int i=0;i<SCC;i++)
            for(int j=0;j<SCC;j++)
                if(g[i][j]!=INF)
                {
                    G[i].push_back(j);
                    ind[j]++;
                }
    }
    int cal2()//對(duì)每個(gè)點(diǎn)，在其鄰接矩陣中找父邊中的最小值
    {
        int ans = 0;
        for(int j=0;j<SCC;j++)
        {
            int Min=INF;
            for(int i=0;i<SCC;i++)
                if(Min>g[i][j])Min=g[i][j];
            if(Min!=INF)ans+=Min;
        }    
        return ans;
    }
    int cal1()
    {
        int s;
        for(int i=0;i<SCC;i++)
        {
            dist[i]=INF;
            if(ind[i]==0)s=i;
        }
        dist[s]=0;
        memset(in,0,sizeof(in));
        in[s]=1;
        queue<int>Q;
        Q.push(s);
        while(!Q.empty())
        {
            int u=Q.front();Q.pop();
            for(int i=0,size=G[u].size();i<size;i++)
            {
                int v=G[u][i];
                if(dist[v]>g[u][v])
                {
                    dist[v]=g[u][v];
                    if(in[v]==0)
                    {
                        in[v]=1;
                        Q.push(v);
                    }
                }
            }
        }
        int ans = 0;
        for(int i=0;i<SCC;i++)
        {
            ans+=dist[i];
        }
        return ans;
    }
}graph;
int main()
{
    //freopen("in","r",stdin);
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        graph.init(n);       
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            graph.add(a,b,c);
        }
        graph.kosaraju();
        graph.build();
        //printf("%d\n",graph.cal1());
        printf("%d\n",graph.cal2());
    }
    return 0;
}