void Flody()
{
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(G[i][j]>G[i][k]+G[k][j])
                {
                    G[i][j]=G[i][k]+G[k][j];
                }
            }
        }
    }
}
//Flody + 路径输出

//初始化，两点间无道路，e[i][j]初始化为正无穷
//	如果两点间有道路，记录每点的后驱 path[i][j] = j;

void flody()
{
    For(k,1,N)
    {
        For(i,1,N)
        {
            For(j,1,N)
            {
                if(e[i][j] == e[i][k] + e[k][j])
                {
                    if(path[i][j] > path[i][k])//找到字典序最小的路path[i][j] = path[i][k];
                }
                if(e[i][j] > e[i][k] + e[k][j])
                {
                    e[i][j] = e[i][k] + e[k][j];
                    path[i][j] = path[i][k];
                }
            }
        }
    }
}

//Bellman-Ford

//存图
int tot;
struct Node
{
    int u, v, w;
} e[4005];
void add(int u, int v, int w)
{
    e[tot].u = u;
    e[tot].v = v;
    e[tot++].w = w;
}
int dis[1005];
int Bellman_Ford(int u, int En)
{
    memset(dis,0x3f,sizeof(dis));
    dis[u] = 0;
    For(i,2,N)
    {
        int check = 1;
        For(j,0,tot)//遍历所有边
        {
            if(dis[ e[j].v ] > dis[ e[j].u ] + e[j].w)
            {
                dis[ e[j].v ] = dis[ e[j].u ] + e[j].w;
                check = 0;
            }
        }
        if(check) break;
    }
    For(j,0,tot)//判断 有无负环
    {
        if(dis[ e[j].v ] > dis[ e[j].u ] + e[j].w) return -1;//存在负环
    }
    int main()
    {
        tot = 0;
        while(M--)	//路径数
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);	//单向边
        }
        printf("%d\n",Bellman_Ford(1,N));
        return 0;
    }

//Bellman-Ford + 队列优化 + 前向星

//存图使用前向星

int dis[1005], cnt[1005];
bool book[1005];

int spfa(int u, int En)
{
    memset(book,false,sizeof(book));
    memset(cnt,0,sizeof(cnt));
    memset(dis,0x3f,sizeof(dis));
    book[u] = 1;
    cnt[u] = 1;
    dis[u] = 0;

    queue<int> q;
    q.push(u);
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        book[u] = 0;
        for(int i = first[u]; ~i; i = e[i].next)
        {
            if(dis[ e[i].v ] > dis[u] + e[i].w)
            {
                dis[ e[i].v ] = dis[u] + e[i].w;

                if(!book[ e[i].v ])
                {
                    q.push(e[i].v);
                    book[e[i].v] = 1;
                    cnt[ e[i].v ]++;
                    if(cnt[ e[i].v ] > N) return -1; //存在负环
                }
            }
        }
    }
    return dis[En];
}