It is assumed that a project consists of a group of subtasks, some of which can be executed in parallel, and some must be executed after completing other subtasks. Task scheduling includes a group of subtasks and the set of subtasks on which each subtask can execute.

For example, completing all courses and graduation design of a major can be regarded as a project to be completed by an undergraduate, and each course can be regarded as a subtask. Some courses can be offered at the same time, such as English and C programming. They do not have the constraint of which course must be taken first; Some courses can not be offered at the same time, because they are dependent on one another. For example, C program design and data structure must be studied first.

However, it should be noted that for A group of subtasks, not any task scheduling is A feasible solution. For example, in the scheme, "subtask A depends on subtask B, subtask B depends on subtask C, and subtask C depends on subtask A", then none of the three tasks can be executed first, which is an infeasible scheme.

In the task scheduling problem, if the time required to complete each sub task is given, we can calculate the shortest time required to complete the whole project. Among these subtasks, even if some tasks are delayed for several days, the global duration will not be affected; However, some tasks must be completed on time, otherwise the construction period of the whole project will be delayed. Such tasks are called "key activities".

Please write a program to determine whether the task scheduling of a given project is feasible; If the scheduling scheme is feasible, calculate the shortest time required to complete the whole project and output all key activities.

Input format:

The first line of input gives two positive integers N(≤ 100) and m, where n is the number of task handover points (i.e. nodes connecting two interdependent subtasks. For example, if task 2 starts after task 1 is completed, there must be a handover point between the two tasks). The handover points are numbered from 1 to N, and M is the number of subtasks, numbered from 1 to M. Then there are three positive integers in M rows, which are the number of the handover point involved in the start and completion of the task and the time required for the task. The integers are separated by spaces.

Output format:

If task scheduling is not feasible, output 0; Otherwise, the first line outputs the time required to complete the whole project, and the second line starts to output all key activities. Each key activity occupies one line and is output in the format "V - > W", where V and W are the handover point numbers involved in the start and completion of the task. The sequence rules for the output of key activities are as follows: the smaller number of the handover point at the beginning of the task takes precedence. When the starting point number is the same, the sequence of the task is opposite to that of the input.

Input example:

7 8
1 2 4
1 3 3
2 4 5
3 4 3
4 5 1
4 6 6
5 7 5
6 7 2

Output example:

17
1->2
2->4
4->6
6->7

The code is as follows:

#include<iostream>
#include<queue>
using namespace std;

int graph[100][100];
int in[100], out[100];
int early[100], late[100];

int earlytime(int N)
{
	int number = 0;
	queue<int> start;

	for (int i = 1; i <= N; i++)
	{
		if (in[i] == 0)
		{
			start.push(i);
		}
	}

	while (start.empty() == false)
	{
		int temp = start.front();
		number++;
		start.pop();

		for (int i = 1; i <= N; i++)
		{
			if (graph[temp][i] != 10000)
			{
				in[i] --;
				early[i] = max(early[i], early[temp] + graph[temp][i]);

				if (in[i] == 0)
				{
					start.push(i);
				}
			}
		}
	}

	if (number != N)
	{
		return -1;
	}
	else
	{
		int max = 0;

		for (int i = 1; i <= N; i++)
		{
			if (early[i] > max)
			{
				max = early[i];
			}
		}

		return max;
	}
}

void latetime(int F, int N)
{
	queue<int> end;

	for (int i = 1; i <= N; i++)
	{
		if (out[i] == 0)
		{
			end.push(i);
			late[i] = F;
		}
	}

	while (end.empty() == false)
	{
		int temp = end.front();
		end.pop();

		for (int i = N; i >= 1; i--)
		{
			if (graph[i][temp] != 10000)
			{
				out[i] --;

				late[i] = min(late[i], late[temp] - graph[i][temp]);

				if (out[i] == 0)
				{
					end.push(i);
				}
			}
		}
	}
}

int main()
{
	int N, M;
	int F;

	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		late[i] = 10000;

		for (int j = 1; j <= N; j++)
		{
			graph[i][j] = 10000;
		}
	}

	for (int i = 0; i < M; i++)
	{
		int work1, work2, time;

		cin >> work1 >> work2 >> time;

		graph[work1][work2] = time;
		in[work2] ++;
		out[work1] ++;
	}

	F = earlytime(N);

	if (F == -1)
	{
		cout << 0;
		return 0;
	}

	latetime(F, N);

	cout << F << endl;

	for (int i = 1; i <= N; i++)
	{
		for (int j = N; j >= 1; j--)
		{
			if (graph[i][j] != 10000 && late[j] - early[i] == graph[i][j])
			{
				cout << i << "->" << j << endl;
			}
		}
	}

	return 0;
}

Topological sorting is used to find critical paths