#include <iostream>
#include <cstring>
using namespace std;
inline int read(){
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+(ch^48),ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

typedef long long ll;
const int N=2e2+5,M=5e4+5;
const ll inf=2e18;
int n,m,u,v;
ll w,d;
ll g[N][N],cg[N][N];
ll dist[4][N],dis[N];
// dist[0/1/2/3][i]: 1->i / n->i / i->1 / i->n
int vis[N],from[N],key[N][N],used[N][N];
struct edge{int u,v;ll w,d;}e[M];

// op: 0/1 正/反图     s(tart)    flg:是否记录最短路树
void dij(int op,int s,ll *dist,bool flg=1){
    for(int i=0; i<=n; i++) dist[i]=1e18,vis[i]=0;
    dist[s]=0;
    while(1){
        u=0;
        for(int i=1; i<=n; i++)
            if(!vis[i] && dist[i]<dist[u])
                u=i;
        if(!u) break;
        vis[u]=1;
        for(int v=1; v<=n; v++){
            w=op==1 ? g[v][u] : g[u][v];
            if(!vis[v] && dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                if(flg) from[v]=u;
            }
        }
    }
    if(flg) for(int i=1; i<=n; i++) key[from[i]][i]=1;
}

/* e.g.1
正图
1 2 4
1 3 2
4 3 1
4 1 6
2 4 2

反图
2 1 4
3 1 2
3 4 1
1 4 6
4 2 2
*/

int main(){
    memset(g,0x3f,sizeof(g)),memset(cg,0x3f,sizeof(cg));
    n=read(),m=read();
    for(int i=1; i<=n; i++) g[i][i]=0;
    for(int i=1; i<=m; i++){
        u=read(),v=read(),w=read(),d=read();
        e[i]={u,v,w,d};
        // 存次小边以供翻转
        if(g[u][v]>w) cg[u][v]=g[u][v],g[u][v]=w;
        else if(cg[u][v]>w) cg[u][v]=w;
    }
    dij(0,1,dist[0]); dij(0,n,dist[1]);
    dij(1,1,dist[2]); dij(1,n,dist[3]);
    ll ans=dist[0][n]+dist[1][1];
    for(int i=1; i<=m; i++){
        u=e[i].u,v=e[i].v,w=e[i].w,d=e[i].d;
        if(!used[u][v] && key[u][v] && w==g[u][v]){ // 最短路树上的边（注意最小）
            used[u][v]=1;
            int t1=g[u][v],t2=g[v][u];
            g[v][u]=min(g[v][u],w);
            g[u][v]=g[u][v]==w ? cg[u][v] : g[u][v]; // 114514
            ll res=d;
            dij(0,1,dis,0); res+=dis[n];  // 1->n
            for(int i=1; i<=n; i++) printf("%lld ",dis[i]); puts("");
            dij(0,n,dis,0); res+=dis[1];  // n->1
            ans=min(ans,res);
            g[u][v]=t1,g[v][u]=t2;
        }else ans=min(ans,1ll*d+min(dist[0][n],dist[0][v]+w+dist[3][u])
                                +min(dist[1][1],dist[1][v]+w+dist[2][u]));
        // 最短路不经过非关键边，可直接翻转后取 dist
    }
    printf("%lld\n",ans>=1e18 ? -1 : ans);
    // printf("%lld\n",ans);
    return 0;
}

前两个样例挂了。

https://www.luogu.com.cn/record/195973627