吉儿是一家古董店的老板娘，由于她经营有道，小店开得红红火火。昨天，吉儿无意之中得到了散落民间几百年的珍宝—月亮之眼。吉儿深知“月亮之眼”价值连城：它是由许多珍珠相连而成的，工匠们用金线连接珍珠，每根金线连接两个珍珠；同时又对每根金线染上两种颜色，一半染成银白色，一半染成黛黑色。由于吉儿自小熟读古籍，所以还晓得“月亮之眼”的神秘传说：“月亮之眼”原是一个古代寺庙的宝物，原本是挂在佛堂的一根顶梁柱上的，整个宝物垂直悬挂，所有珍珠排成一线，且都镶嵌在柱子里，而每一根金线又都是绷紧的，并且金线的银白色一端始终在黛黑色一端的上方；然而，在一个月圆之夜，“月亮之眼”突然从柱里飞出，掉落下来，宝物本身完好无损，只是僧侣们再也无法以原样把“月亮之眼”嵌入柱子中了。吉儿望着这个神秘的宝物，回忆着童年读到的传说，顿时萌发出恢复“月亮之眼”的冲动，但是摆弄了几天依旧没有成功。

现在，要麻烦您来帮助吉儿完成这项使命。

您要设计一个程序，对于给定的“月亮之眼”进行周密分析，然后给出这串宝物几百年前嵌在佛堂顶梁柱上的排列模样。给定的“月亮之眼”有N个珍珠和P根金线，所有珍珠按一定顺序有了一个序号：1、2…、N。

输入格式

输出格式

#include<cstdio>

#include<cstring>

#include<vector>

#include<queue>

using namespace std;

const int MAXN=;

const int INF=0x7f7f7f7f;

struct Edge{

    int to,w;

    Edge(){}

    Edge(int  to,int w)

    {

        this->to=to;

        this->w=w;

    }

};

vector<Edge> mp[MAXN];

int d[MAXN],vis[MAXN];

int cnt[MAXN];

int n,m;

bool bfs(int u)

{

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

    {

        d[i]=INF;

        vis[i]=;

    }

    queue<int> que;

    d[u]=;

    vis[u]=;

    que.push(u);

    while(!que.empty())

    {

        int now=que.front();que.pop();

        for(int i=;i<mp[now].size();i++)

        {

            Edge e=mp[now][i];

            int l=d[now]+e.w;

            if(vis[e.to]&&l!=d[e.to])

            {

                return false;

            }

            else if(!vis[e.to])

            {

                que.push(e.to);

                vis[e.to]=;

                d[e.to]=l;

            }

        }

    }

    return true;

}

int main()

{

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

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

    {

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        mp[u].push_back(Edge(v,w));

        mp[v].push_back(Edge(u,-w));

    }

    if(bfs())

    {

        int mn=INF;

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

        {

            if(d[i]<mn)

            {

                mn=d[i];

            }

        }

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

        {

            d[i]-=mn;

        }

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

        {

            printf("%d",d[i]);

            if(i!=n)

                printf("\n");

        }

    }

    else

        printf("-1\n");

    return ;

}