#include 
      
       #define pb push_back#define _for(i,a,b) for(int i = (a);i < (b);i ++)#define INF 0x3f3f3f3fusing namespace std;const int maxn = 50003;struct edge{    int to;    int cost;};vector
       
         G[maxn];//G[s].push_back(t);from s to t,directedint V,E;//from s to other Vvoid shortest_path(int s){    }int main(){    scanf("%d %d",&V,&E);    _for(i,0,E)    {        int s,t,c;        scanf("%d %d %d",&s,&t,&c);        G[s].push_back(edge{t,c});        G[t].push_back(edge{s,c});    }    shortest_path(0);    cout << d[6] << endl;}/*101 22 52 43 63 24 105 15 36 56 9*/
       
      

//from s to other Vint d[maxn];void shortest_path(int s){    _for(i,0,V)        d[i] = INF;    d[s] = 0;    while(1)    {        bool update = false;        _for(i,0,V)        {            _for(j,0,G[i].size())            {                edge e = G[i][j];                if(d[i] != INF && d[e.to] > d[i] + e.cost)                {                    d[e.to] = d[i] + e.cost;                    update = true;                }            }        }        if(!update) break;    }}

//from s to other Vbool used[maxn];int d[maxn];void shortest_path(int s){    _for(i,0,V)    {        d[i] = INF;        used[i] = false;    }    d[s] = 0;    while(1)    {        int v = -1;        _for(i,0,V)        if(!used[i] && (v==-1 || d[i] < d[v])) v = i;        if(v==-1) break;        used[v] = true;        _for(i,0,G[v].size())        d[G[v][i].to] = min(d[G[v][i].to],d[v]+G[v][i].cost);    }}

//from s to other Vtypedef pair
      
        P;//first 是最短距离，second 是顶点编号 int d[maxn];void shortest_path(int s){    priority_queue
       
        
,greater
        
> que;        _for(i,0,V)        d[i] = INF;    d[s] = 0;    que.push(P{
     0,s});    while(!que.empty())    {        P p = que.top();que.pop();        int v = p.second;        if(d[v] < p.first) continue;        _for(i,0,G[v].size())        {            edge e = G[v][i];            if(d[e.to] > d[v] + e.cost)            {                d[e.to] = d[v] + e.cost;                que.push(P{d[e.to],e.to});            }        }    }}
       
      

//from s to other Vtypedef pair
      
        P;//first 是最短距离，second 是顶点编号 int d[maxn];int pre[maxn];void shortest_path(int s){    priority_queue
       
        
,greater
        
> que;        _for(i,0,V)        d[i] = INF;    _for(i,0,V)        pre[i] = -1;    d[s] = 0;    que.push(P{
     0,s});    while(!que.empty())    {        P p = que.top();que.pop();        int v = p.second;        if(d[v] < p.first) continue;        _for(i,0,G[v].size())        {            edge e = G[v][i];            if(d[e.to] > d[v] + e.cost)            {                d[e.to] = d[v] + e.cost;                que.push(P{d[e.to],e.to});                pre[e.to] = v;            }        }    }}//到终点t vector
         
           get_path(int t){    vector
          
            p;    for(; t != -1;t = pre[t]) p.pb(t);    reverse(p.begin(),p.end());    return p;}
          
         
       
      

bool find_negative_loop(){    memset(d,0,sizeof(d));    _for(i,0,V)        _for(j,0,V)            _for(k,0,G[j].size())            {                edge e = G[j][k];                if(d[e.to] > d[j] + e.cost)                {                    d[e.to] = d[j] + e.cost;                    if(i==V-1) return true;                }            }    return false;}

//from s to other Vint d[maxn][maxn];void shortest_path(){    memset(d,INF,sizeof(d));    _for(i,0,V)        _for(j,0,G[i].size())        {            edge e = G[i][j];            d[i][e.to] = e.cost;        }        _for(k,0,V)        _for(i,0,V)            _for(j,0,V)                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);}

//from s to other V//return false表示有负圈int d[maxn];// 距离数组 int vis[maxn];// 判断点是否在队列里 int pre[maxn];// 路径还原int cnt[maxn];// 进队列次数 bool shortest_path(int s){    memset(d,INF,sizeof(d));    memset(vis,0,sizeof(vis));    memset(cnt,0,sizeof(cnt));    memset(pre,-1,sizeof(pre));        deque
      
        q;    d[s] = 0,cnt[s] = vis[s] = 1;    q.push_back(s);    while(!q.empty())    {        int now = q.front();q.pop_front();        vis[now] = 0;        _for(i,0,G[now].size())        {            if(d[G[now][i].to] > d[now] + G[now][i].cost)            {                d[G[now][i].to] = d[now] + G[now][i].cost;                pre[G[now][i].to] = now;                if(!vis[G[now][i].to])                {                    if(V == ++cnt[G[now][i].to]) return false;                    if(!q.empty() && d[G[now][i].to] < d[q.front()])//队列非空且优于队首（SLF）                        q.push_front(G[now][i].to);                    else q.push_back(G[now][i].to);                    vis[G[now][i].to] = 1;                }            }        }    }    return 0;}//到终点t vector
       
         get_path(int t){    vector
        
          p;    for(; t != -1;t = pre[t]) p.pb(t);    reverse(p.begin(),p.end());    return p;}
        
       
      

Bellman O(|V|*|E|)，可处理负边

Dijkstra 优先队列实现 O(|E|*log|V|)，不可处理负边

Floyd O(|V^3|) d[i][i]为负数时可判定有负圈

SPFA O(|V|*|E|)，如果返回false则有负圈