Yet Another DAG Problem
Contest: Educational Codeforces Round 96 (Rated for Div. 2)
Difficulty rating: 2600
Tags: bitmasks, dfs and similar, dp, flows, graphs, math

You are given a directed acyclic graph (a directed graph that does not contain cycles) of $$$n$$$ vertices and $$$m$$$ arcs. The $$$i$$$-th arc leads from the vertex $$$x_i$$$ to the vertex $$$y_i$$$ and has the weight $$$w_i$$$.

Your task is to select an integer $$$a_v$$$ for each vertex $$$v$$$, and then write a number $$$b_i$$$ on each arcs $$$i$$$ such that $$$b_i = a_{x_i} - a_{y_i}$$$. You must select the numbers so that:

- all $$$b_i$$$ are positive;
- the value of the expression $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ is the lowest possible.

It can be shown that for any directed acyclic graph with non-negative $$$w_i$$$, such a way to choose numbers exists.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 18$$$; $$$0 \le m \le \dfrac{n(n - 1)}{2}$$$).

Then $$$m$$$ lines follow, the $$$i$$$-th of them contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$1 \le w_i \le 10^5$$$, $$$x_i \ne y_i$$$) — the description of the $$$i$$$-th arc.

It is guaranteed that the lines describe $$$m$$$ arcs of a directed acyclic graph without multiple arcs between the same pair of vertices.

Output format:
Print $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_v \le 10^9$$$), which must be written on the vertices so that all $$$b_i$$$ are positive, and the value of the expression $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ is the lowest possible. If there are several answers, print any of them. It can be shown that the answer always exists, and at least one of the optimal answers satisfies the constraints $$$0 \le a_v \le 10^9$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Example input:
3 2
2 1 4
1 3 2

Example output:
1 2 0

Example input:
5 4
1 2 1
2 3 1
1 3 6
4 5 8

Example output:
43 42 41 1337 1336

Editorial:
The key observation in this problem is that the values of $$$a_v$$$ should form a contiguous segment of integers. For example, suppose there exists a value $$$k$$$ such that there is at least one $$$a_v < k$$$, there is at least one $$$a_v > k$$$, but no $$$a_v = k$$$. We can decrease all values of $$$a_v$$$ that are greater than $$$k$$$ by $$$1$$$, so the answer will still be valid, but the value of $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ will decrease. So, the values of $$$a_v$$$ form a contiguous segment of integers. We can always assume that this segment is $$$[0, n - 1]$$$, since subtracting the same value from each $$$a_v$$$ does not change anything.
The other observation we need is that we can rewrite the expression we have to minimize as follows: $$$\sum \limits_{i = 1}^{m} w_i b_i = \sum \limits_{v = 1}^{n} a_v c_v$$$, where $$$c_v$$$ is the signed sum of weights of all arcs incident to the vertex $$$v$$$ (the weights of all arcs leading from $$$v$$$ are taken with positive sign, and the weights of all arcs leading to $$$v$$$ are taken with negative sign). These two observations lead us to a bitmask dynamic programming solution: let $$$dp_{i, mask}$$$ be the minimum value of $$$\sum \limits_{v = 1}^{n} a_v c_v$$$, if we assigned the values from $$$[0, i - 1]$$$ to the vertices from $$$mask$$$. A naive way to calculate this dynamic programming is to iterate on the submask of $$$mask$$$, check that choosing the integer $$$i - 1$$$ for each vertex from that submask doesn't ruin anything (for each vertex that belongs to this submask, all vertices that are reachable from it should have $$$a_v < i - 1$$$, so they should belong to $$$mask$$$, but not to the submask we iterate on), and update the dynamic programming value. But this solution is $$$O(n 3^n)$$$, and, depending on your implementation, this might be too slow.
It's possible to speed this up to $$$O(n^2 2^n)$$$ in a way similar to how profile dp can be optimized from $$$O(3^n)$$$ to $$$O(n 2^n)$$$: we won't iterate on the submask; instead, we will try to add the vertices one by one, and we should be able to add a vertex to the mask only if all vertices that are reachable from it already belong to the mask. There is a possibility that we add two vertices connected by an arc with the same value of $$$a_v$$$, so, for a fixed value of $$$a_v$$$, we should consider assigning it to vertices in topological sorting order (that way, if one vertex is reachable from another, it will be considered later, so we won't add both of those with the same value of $$$a_v$$$).