闷热的夏天,威斯康辛州的奶制品地区提供冷水供奶牛饮用，以此来解渴。农夫约翰将冷水通过N (3 <= N <= 99999; N 为奇数)个冷水管道，分别编号序号1..N从泵的位置一直送到牛棚里。当水在管道中流动时，夏天的热能使它变热。贝茜想要找到最冷的水,这样她就能比任何其他奶牛更好地享受这难得的好天气。

她已经绘制了一整套完整的分支管道,并注意到这个管道系统犹如一棵树,它的根在农场,从根开始每个分支都分离出两个管道。令人惊讶的是，所有管道都有一个长度，当然这所有的N根管道连接成1条路或者和其他的管道路线连接。

给出所有管道连接的地图，计算每一个分支点到牛棚的距离。贝茜将通过这些信息来找到最清凉冷水。

管道的端点，可以作为分支点也可以作为管道终点，它以管道的编号命名。地图上包含C (1<= C <= N)个分支器，每个分支器包含3个数据，管道端点E_i (1<= E_i <= N)，管道端点连接的两个管道B1_i, B2_i (2<= B1_i <=N; 2<= B2_i <=N)。管道1连接到牛棚，每两个连接器之间的管道长度均为1。

* 第 1 行: 2个用空格隔开的整数 N , C

* 第 2 至 C+1 行: 3个用空格隔开的整数，分别表示连接器的编号，以及连接的2个管道的编号E_i, B1_i, B2_i

* 共 N 行: 分别表示每个管道到牛棚的最短距离。

5 2

3 5 4

1 2 3

1

2

2

3

3

+------+

| Barn |

+------+

|  1

*

2 / \ 3

*

4 / \ 5

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int MAXN=;

 const int maxn=0x7fffffff;

 struct node

 {

     int u;

     int v;

     int w;

     int next;

 }edge[MAXN];

 int num=;

 int head[MAXN];

 int dis[MAXN];

 int vis[MAXN];

 void spfa()

 {

     dis[]=;

     vis[]=;

     queue<int>q;

     q.push();

     while(q.size()!=)

     {

         int p=q.front();

         q.pop();

         for(int i=head[p];i!=-;i=edge[i].next)

         {

             int to=edge[i].v;

             if(dis[to]>dis[p]+edge[i].w)

             {

                 dis[to]=dis[p]+edge[i].w;

                 if(vis[to]==)

                 {

                     vis[to]=;

                     q.push(to);

                 }

             }

         }

     }

 }

 int main()

 {

     int n,m;

     scanf("%d%d",&n,&m);

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

     {

         head[i]=-;

         dis[i]=maxn;

     }

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

     {

         int x,y,z;

         scanf("%d%d%d",&x,&y,&z);

         edge[num].u=x;

         edge[num].v=y;

         edge[num].w=;

         edge[num].next=head[x];

         head[x]=num++;

         edge[num].u=x;

         edge[num].v=z;

         edge[num].w=;

         edge[num].next=head[x];

         head[x]=num++;

     }

     spfa();

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

     {

         printf("%d\n",dis[i]+);

     }

     return ;

 }