题目大意

给n个点m条无向边，每条边有边权，当点1到点i的最短路的最后一条边被封住时（只有最后一条边，其他边还可以用），求点1到点i的最短路，i取2，3，……，n（被封住边只影响此次的结果，不影响其他点的结果）,如果被封住后到达不了i，则输出-1，否则输出被封住边后的最短路

解题思路

思维过程

我们肯定要先跑一遍单源最短路，此时，我们得到了从点1到任意点的最短距离（后文用dist数组表示）
设到i的最短路径上除i以外，最后一个点为x，我们考虑另一条经过y的路径，如果i与y有边，那就判断是否更新答案 ,其中val表示i与y的边的边权，那么我们只需要考虑与i相连的除了x以外的所有点即可，
但是，直接这样做会出现问题：可能i在y的路径上，因为我们计算dist[y]的时候，会经过i-x这条边，但是，这显然是不符合题意的，于是，我们想到了一种解决办法：建立一颗由最短路路径构成的树！

首先，为什么最短路路径构成的一定是树？

由于题目已经说了，到每个点的最短路是唯一的（题目最后一句话），所以我们只要沿着最短路遍历（即满足dist[v]==dist[v]+val才走），最后一定会构成一颗树

这颗树有什么用呢？

我们更新i点的答案时，只使用非i子节点的y点，即 这样就能避免上面提到的问题（删边不影响非子节点），
但是，这样又出现了新的问题，我们遗漏了一种情况

如图，黑色为最短路径生成树，红色手写线表示删边后的最短路，红色直线表示不在生成树中的边
我们发现，可能会存在通过i的子节点来更新i的情况，此时，有 ，其中，val表示y与y'的边权，注意：此处的y'不一定是i的直接子节点，也可以是子节点的子节点的子节点之类的，并且，我们发现，在这个环中，所有点的答案都可以表示为dist[y]+dist[y']+val-dist[i],i取y到lca(y,y')以及y'到lca(y,y')

最终解法

先跑一遍最短路，然后沿最短路遍历一遍，此时考虑所有未被遍历的边，将这些边的dist[u]+dist[v]+val放入小根堆中，（用小根堆保证答案是最优，这样我们每个点只需要更新一遍），每次取堆顶元素，向上更新到lca，用并查集来控制每个点只在第一次遇到时更新（更新后就把点和父节点放在同一个集合里，当两个点的集合相同时停止继续向上更新）

代码实现

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int mx=200010;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
int n,m;
int dist[mx];
int ans[mx];
int top=1;
int head[mx];
struct Edge{
    int u;
    int val;
    int v;
    int next;
}edge[mx<<1];
void addedge(int u,int v,int val){
    edge[++top].val=val;
    edge[top].v=v;
    edge[top].u=u;
    edge[top].next=head[u];
    head[u]=top;
}
void add(int u,int v,int val){
    addedge(u,v,val);
    addedge(v,u,val);
} 
struct Node{
    int u;
    int di;
};
struct cmp{
    bool operator ()(const Node &a,const Node &b)const{
    return a.di>b.di;
    }
};

bool vis[mx];
void dijkstra(){
    memset(dist,0x7f,sizeof(dist));
    priority_queue<Node,vector<Node>,cmp>q;
    q.push((Node){1,0});
    dist[1]=0;
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].v;
            int val=edge[i].val;
            if(dist[v]>dist[u]+val){
                dist[v]=dist[u]+val;    
                if(!vis[v]){
                q.push((Node){v,dist[v]});
                }    
            }    

        }    
    }
    return;
}
int fa[mx],dep[mx];
bool vis_edge[mx];
void dfs(int u,int f){//沿最短路遍历 
    fa[u]=f;
    dep[u]=dep[f]+1;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        int val=edge[i].val;
        if(dist[v]==dist[u]+val){
            vis_edge[i]=1;//标记最短路树上的边 
            dfs(v,u);
        }
    }
} 
struct Path{
    int u,v,sum_val;//每个环路径的u和v和总长度 
};
struct cm{
    bool operator()(const Path &a,const Path &b)const{
    return a.sum_val>b.sum_val;
    }
};
int set[mx];
int find(int x){
    return set[x]=set[x]==x?x:find(set[x]);
}
int main(){
    n=Read(),m=Read();
    for(int i=1;i<=m;++i){
        int u=Read(),v=Read(),val=Read();
        add(u,v,val);
    }
    dijkstra();//跑一遍最短路求出所有点到1的最短距离dist 
    dfs(1,1);//沿着最短路遍历整个图（最短路形成的树），求出每个点的深度和父亲节点 
    priority_queue<Path,vector<Path>,cm>q; 
    for(int i=2;i<=top;i+=2){
        if(vis_edge[i])continue;
        int u=edge[i].u;
        int v=edge[i].v;
        Path now;
        now.u=u,now.v=v,now.sum_val=dist[u]+dist[v]+edge[i].val;
        q.push(now);
    } 
    memset(ans,-1,sizeof(ans));
    for(int i=1;i<=n;++i)set[i]=i;
    while(!q.empty()){
        Path now=q.top();
        q.pop();
        int u=now.u,v=now.v,val=now.sum_val;
        u=find(u),v=find(v);
        while(u!=v){
            if(dep[u]>dep[v])swap(u,v);
            ans[v]=val-dist[v];
            set[v]=set[fa[v]];
            v=find(fa[v]);
        }
    }
    for(int i=2;i<=n;++i)printf("%d\n",ans[i]);
    return 0;
}