Eva

Description

* 第一行: 两个空格分开的数, N和M

* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output

* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

Sample Input

4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
输入解释:
跟题中例子相同

Sample Output

3
3
6
输出解释:
跟题中例子相同

/**************************************************************

    Problem: 1576

    User: ictsing

    Language: C++

    Result: Accepted

    Time:4184 ms

    Memory:42008 kb

****************************************************************/

 

//BZOJ1576 [Usaco2009 Jan]安全路经Travel

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <queue>

using namespace std;

int ecnt=0;

const int mt = 200000+5;

const int inf = 2e9;

typedef pair<int,int> pa;

int dis[mt];

int fr[mt],w[mt<<1],nxt[mt<<1],to[mt<<1],adj[mt];

bool mark[mt<<1];

int x[mt],y[mt];

int val[mt<<2],tag[mt<<2];

typedef long long ll;

bool vis[mt];

int n,m;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void adde(int u,int v,int ww)

{

    ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],w[ecnt]=ww,adj[u]=ecnt;

    ecnt++,to[ecnt]=u,nxt[ecnt]=adj[v],w[ecnt]=ww,adj[v]=ecnt;

}

priority_queue< pa,vector<pa> ,greater<pa> >q;

void dk()

{

    while(!q.empty()) q.pop();

    memset(dis,127,sizeof(dis));

    dis[1]=0;q.push(make_pair(0,1));

    while(!q.empty())

    {

        pa u=q.top();q.pop();

        if(vis[u.second]) continue;

        vis[u.second]=1;

        for(int i=adj[u.second];i;i=nxt[i])

        {

            int v=to[i];

            if(dis[v]>u.first+w[i])

            {

                mark[fr[v]]=0;

                fr[v]=i;

                mark[fr[v]]=1;

                dis[v]=u.first+w[i];

                q.push(make_pair(dis[v],v));

            }

        }

    }

}

int f[mt][26],dep[mt],sz[mt],opt[mt];

int top[mt];

void dfs1(int u,int fa)

{

    f[u][0]=fa;

    dep[u]=dep[fa]+1;

    sz[u]=1;

    for(int i=adj[u];i;i=nxt[i])

    {

        if(!mark[i]) continue;

        int v=to[i];

        if(v==fa) continue;

        dfs1(v,u);

        sz[u]+=sz[v];

        if(sz[v]>sz[opt[u]])

            opt[u]=v;

    }

}

int pl[mt];

int _clock=0;

void dfs2(int u,int chain)

{

    top[u]=chain;

    pl[u]=++_clock;

    if(opt[u]) dfs2(opt[u],chain);

    else return ;

    for(int i=adj[u];i;i=nxt[i])

    {

        if(!mark[i]) continue;

        int v=to[i];

        if(v==f[u][0]||v==opt[u]) continue;

        dfs2(v,v);

    }

}

void init()

{

    for(int i=1;i<=16;i++)

        for(int j=1;j<=n;j++)

            f[j][i]=f[f[j][i-1]][i-1];

}

int lca(int u,int v)

{

    if(dep[u]<dep[v]) swap(u,v);

    for(int i=0;i<=16;i++)

        if((dep[u]-dep[v])&(1<<i)) u=f[u][i];

    for(int i=16;i>=0;i--)

        if(f[u][i]!=f[v][i])

            u=f[u][i],v=f[v][i];

    if(u==v) return u;

    return f[u][0];

}

void build(int rt,int l,int r)

{

    val[rt]=inf;tag[rt]=inf;

    if(l==r) return ;

    int mid=(l+r)>>1;

    build(rt<<1,l,mid);

    build(rt<<1|1,mid+1,r);

}

void pushdown(int rt)

{

    if(tag[rt]==inf) return ;

    tag[rt<<1]=min(tag[rt<<1],tag[rt]);

    tag[rt<<1|1]=min(tag[rt<<1|1],tag[rt]);

    val[rt<<1]=min(val[rt<<1],tag[rt]);

    val[rt<<1|1]=min(val[rt<<1|1],tag[rt]);

    tag[rt]=inf;

}

int query(int rt,int l,int r,int pos)

{

    if(l==r) return val[rt];

    int mid=(l+r)>>1;

    pushdown(rt);

    if(pos<=mid) return query(rt<<1,l,mid,pos);

    else return query(rt<<1|1,mid+1,r,pos);

}

void update(int rt,int l,int r,int lft,int rgt,int pwp)

{

    if(lft>rgt) return ;

    if(lft<=l&&r<=rgt)

    {

        tag[rt]=min(tag[rt],pwp);

        val[rt]=min(val[rt],pwp);

        return ;

    }

    pushdown(rt);

    int mid=(l+r)>>1;

    if(lft<=mid) update(rt<<1,l,mid,lft,rgt,pwp);

    if(mid<rgt) update(rt<<1|1,mid+1,r,lft,rgt,pwp);

}

void lca_update(int u,int v,int ovo)//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

{

    while(top[u]!=top[v])

    {

        update(1,1,n,pl[top[u]],pl[u],ovo);

        u=f[top[u]][0];

    }

    if(u!=v) update(1,1,n,pl[v]+1,pl[u],ovo);

}

int main()

{

    n=read(),m=read();

    memset(f,-1,sizeof(f));

    for(int i=1;i<=m;i++)

    {

        x[i]=read(),y[i]=read();

        int qwq=read();

        adde(x[i],y[i],qwq);

        //adde(y[i],x[i],qwq);

    }

    dk();

    dfs1(1,0);

    init();

    dfs2(1,1);

    build(1,1,n);

    //for(int i=1;i<=n;i++)

        //cout<<i<<" "<<pl[i]<<" qwq "<<endl;

    for(int i=1;i<=m;i++)

    {

        int qwq=lca(x[i],y[i]);//cout<<qwq<<" fuck "<<endl;

        if(!mark[2*i-1]) lca_update(y[i],qwq,dis[x[i]]+dis[y[i]]+w[2*i-1]);

        if(!mark[2*i]) lca_update(x[i],qwq,dis[y[i]]+dis[x[i]]+w[2*i]);

    }

    for(int i=2;i<=n;i++)

    {

        int tmp=query(1,1,n,pl[i]);

        if(tmp!=inf) printf("%d\n",tmp-dis[i]);

        else puts("-1");

    }

    return 0;

}