In my opinion, people are divided into two categories: some live in the future while others — in the past. Should it be explained what category did I belong? The mystery I hunted for a half of my life, finally was taking shape. Good Magician didn't know where Dragon hid. But he knew that bandit dens in some cities of the kingdom were controlled by people from the Dragon's gang. For each city he gave me a reliable information, whether Dragon controlled that city or not.

I was staring on the map of Fairy Kingdom trying to understand where to go now. There were n cities in the Kingdom, connected by mroads, with the length of the j-th road equal to wj. I guessed that Dragon hid in one of two cities controlled by his gang with the shortest path between them. First of all, the traffic of Blue Tea was the highest between them, and secondly, in case of emergency it was possible to move quickly from one of the cities to the other. All that remained was just to find such pair of cities.

The first line contains two integers separated by a space: n and m (2?≤?n?≤?105, 1?≤?m?≤?105) — the number of cities in Fairy Kingdom and the number of roads between them, correspondingly.

The second line contains n integers separated by spaces. On the i-th position the number 1 is written, if the i-th city is under control of Dragon's gang; otherwise the number 0 is written there.

The next m lines contain three integers each, separated by spaces: ai, bi, wi (1?≤?ai?<?bi?≤?n, 1?≤?wi?≤?109) — the numbers of cities connected by a road and the length of this road. The cities are numbered from 1. Each pair of cities is PResented at most once.

In the first line output a single integer — the length of the shortest path between cities where Dragon presumably hides.

In the second line output two integers separated by a space — the numbers of these cities.

If there are several possible answers, output any of them. If no two cities controlled by Dragon's people have a path between them, output ?No luck at all? without quotes.

4 41 0 0 11 2 11 3 22 4 33 4 1output
34 1input
7 91 0 1 1 0 0 11 2 51 4 1002 3 52 5 42 6 43 7 1004 5 26 7 25 6 3output
74 7input
2 10 01 2 1output
No luck at all
題意：城市有兩種屬性(0/1),找最近的兩個屬性為1的城市，輸出最短路長度與起點終點。題解：SPFA變形，單源最短路轉化為，所有點到某個1之間的最短路，然后枚舉中間邊，找合法解。解法：SPFA，將所有1點同時初始化為0，同時進棧進行松弛，最終可求出每一點到最近的1的距離及最近的1是哪個點。然后遍歷所有邊，若一條邊兩邊都是1，則路徑合法；若兩邊都是0，且兩邊最近的1不同點，則路徑合法；若一邊0一邊1，且兩邊最近的1不同點，則路徑合法。最后將所有合法路徑取最小值即為答案。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const ll inf=9e18;const ll mod=1000000007;const int maxn=1e5+100;int head[maxn];struct edge{    int from,to,next;    ll w;}e[maxn*2];   //int tol=0;void add(int u,int v,ll w){    e[++tol].to=v,e[tol].from=u,e[tol].next=head[u],e[tol].w=w,head[u]=tol;}int a[maxn];ll d[maxn];int pre[maxn];int q[maxn],inq[maxn];int main(){    int n,m;    scanf("%d%d",&n,&m);    rep(i,1,n+1) scanf("%d",&a[i]);    while(m--)    {        int u,v;        ll w;        scanf("%d%d%I64d",&u,&v,&w);        add(u,v,w),add(v,u,w);    }    int front=0,rear=0;    rep(i,1,n+1) d[i]=inf;    rep(i,1,n+1)    {        if(a[i])        {            q[rear++]=i,inq[i]=1,d[i]=0,pre[i]=i;        }    }    while(front!=rear)    {        int u=q[front++];        if(front>=maxn) front=0;        inq[u]=0;        for(int i=head[u];i;i=e[i].next)        {            int v=e[i].to;            ll w=e[i].w;            if(d[u]+w<d[v])            {                d[v]=d[u]+w;                pre[v]=pre[u];                if(inq[v]) continue;                q[rear++]=v;                inq[v]=1;                if(rear>=maxn) rear=0;            }        }    }    ll ans=inf;    int u,v;    for(int i=0;i<=tol;i+=2)    {        int u1=e[i].from,v1=e[i].to;        if(a[u1]&&a[v1])        {            if(e[i].w<ans)                ans=e[i].w,u=u1,v=v1;        }        else if(a[u1])        {            if(pre[v1]!=u1)            {                if(e[i].w+d[v1]<ans)                {                    ans=e[i].w+d[v1];                    u=u1,v=pre[v1];                }            }        }        else if(a[v1])        {            if(pre[u1]!=v1)            {                if(e[i].w+d[u1]<ans)                {                    ans=e[i].w+d[u1];                    u=pre[u1],v=v1;                }            }        }        else        {            if(pre[v1]!=pre[u1])            {                if(e[i].w+d[v1]+d[u1]<ans)                {                    ans=e[i].w+d[v1]+d[u1];                    u=pre[u1],v=pre[v1];                }            }        }    }    if(ans>=inf) puts("No luck at all");    else    {        printf("%I64d/n%d %d/n",ans,u,v);    }    return 0;}