Problem: 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 ∑ _{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

The first line contains two integers n and m (2 ≤ n ≤ 18; 0 ≤ m ≤ (n(n - 1))/(2)).

Then m lines follow, the i-th of them contains three integers x_i, y_i and w_i (1 ≤ x_i, y_i ≤ n, 1 ≤ w_i ≤ 10^5, x_i ≠ 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

Print n integers a_1, a_2, ..., a_n (0 ≤ a_v ≤ 10^9), which must be written on the vertices so that all b_i are positive, and the value of the expression ∑ _{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 ≤ a_v ≤ 10^9.

Examples

Input


3 2
2 1 4
1 3 2


Output


1 2 0


Input


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


Output


43 42 41 1337 1336


Input


5 5
1 2 1
2 3 1
3 4 1
1 5 1
5 4 10


Output


4 3 2 1 2

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 27);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            PrintWriter out = new PrintWriter(outputStream);
            GYetAnotherDAGProblem solver = new GYetAnotherDAGProblem();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class GYetAnotherDAGProblem {
        public void solve(int testNumber, FastInput in, PrintWriter out) {
            int n = in.readInt();
            int m = in.readInt();
            DualLinearProgramming lp = new DualLinearProgramming(m, n, 1e-10);
            int[] weights = new int[n];
            for (int i = 0; i < m; i++) {
                int a = in.readInt();
                int b = in.readInt();
                int w = in.readInt();
                weights[a - 1] += w;
                weights[b - 1] -= w;
                lp.setConstraintCoefficient(i + 1, a, 1);
                lp.setConstraintCoefficient(i + 1, b, -1);
                lp.setConstraintConstant(i + 1, 1);
            }
            for (int i = 0; i < n; i++) {
                lp.setTargetCoefficient(i + 1, weights[i]);
            }
            lp.solve();
            assert !lp.isInfeasible();
            assert !lp.isUnbound();
            for (int i = 0; i < n; i++) {
                long x = Math.round(lp.getAssignmentValueForVariable(i + 1));
                out.print(x);
                out.append(' ');
            }
        }

    }

    static class LinearProgramming {
        private final double prec;
        private final double inf = 1e50;
        double[][] mat;
        int[] basicVariables;
        int[] basicVariable2RowIndex;
        private boolean unbound;
        private boolean infeasible;
        int n;
        int m;

        public LinearProgramming(int n, int m, double prec) {
            this.prec = prec;
            this.n = n;
            this.m = m + n;
            mat = new double[n + 1][this.m + 2];
            basicVariables = new int[this.m + 2];
            basicVariable2RowIndex = new int[this.m + 2];
            for (int i = 1; i <= this.m; i++) {
                if (i <= m) {
                    basicVariable2RowIndex[i] = -1;
                } else {
                    basicVariable2RowIndex[i] = i - m;
                    basicVariables[i - m] = i;
                }
            }
        }

        public void setConstraintConstant(int constraintId, double noMoreThan) {
            mat[constraintId][0] = noMoreThan;
        }

        public void setConstraintCoefficient(int constraintId, int variableId, double c) {
            mat[constraintId][variableId] = -c;
        }

        public void setTargetCoefficient(int variableId, double c) {
            mat[0][variableId] = c;
        }

        public double maxSolution() {
            return mat[0][0];
        }

        public boolean isInfeasible() {
            return infeasible;
        }

        public boolean isUnbound() {
            return unbound;
        }

        public double getAssignmentValueForVariable(int i) {
            if (basicVariable2RowIndex[i] == -1) {
                return 0;
            } else {
                return mat[basicVariable2RowIndex[i]][0];
            }
        }

        private boolean initSimplex() {
            if (n == 0) {
                return true;
            }
            int minConstantRow = 1;
            for (int i = 2; i <= n; i++) {
                if (mat[i][0] < mat[minConstantRow][0]) {
                    minConstantRow = i;
                }
            }
            if (mat[minConstantRow][0] >= 0) {
                return true;
            }
            double[] originalTargetExpression = mat[0];
            m++;
            mat[0] = new double[m + 1];
            mat[0][m] = -1;
            basicVariable2RowIndex[m] = -1;
            for (int i = 1; i <= n; i++) {
                mat[i][m] = 1;
            }
            pivot(m, minConstantRow);
            while (simplex()) ;
            if (mat[0][0] != 0 || unbound) {
                infeasible = true;
                unbound = false;
                return false;
            }
            if (basicVariable2RowIndex[m] != -1) {
                int row = basicVariable2RowIndex[m];
                int firstNegativeVariable = -1;
                for (int i = 1; i <= m && firstNegativeVariable == -1; i++) {
                    if (mat[row][i] != 0) {
                        firstNegativeVariable = i;
                    }
                }
                pivot(firstNegativeVariable, row);
            }

            //restore
            m--;
            mat[0] = originalTargetExpression;
            for (int i = 1; i <= m; i++) {
                if (basicVariable2RowIndex[i] == -1) {
                    continue;
                }
                int row = basicVariable2RowIndex[i];
                double c = mat[0][i];
                for (int j = 0; j <= m; j++) {
                    if (j == i) {
                        mat[0][j] = 0;
                        continue;
                    }
                    mat[0][j] += mat[row][j] * c;
                }
            }
            normalize();
            return true;
        }

        public void solve() {
            if (!initSimplex()) {
                return;
            }
            while (simplex()) ;
        }

        private void normalize() {
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= m; j++) {
                    if (mat[i][j] >= -prec && mat[i][j] <= prec) {
                        mat[i][j] = 0;
                    }
                }
            }
        }

        private void pivot(int variableId, int row) {
            int basicVariableId = basicVariables[row];
            mat[row][basicVariableId] = -1;
            for (int i = 0; i <= m; i++) {
                if (i == variableId) {
                    continue;
                }
                mat[row][i] /= -mat[row][variableId];
            }
            mat[row][variableId] = -1;
            basicVariables[row] = variableId;
            basicVariable2RowIndex[basicVariableId] = -1;
            basicVariable2RowIndex[variableId] = row;
            for (int i = 0; i <= n; i++) {
                if (i == row || mat[i][variableId] == 0) {
                    continue;
                }
                double c = mat[i][variableId];
                for (int j = 0; j <= m; j++) {
                    if (j == variableId) {
                        mat[i][j] = 0;
                        continue;
                    }
                    mat[i][j] += mat[row][j] * c;
                }
            }
            normalize();
        }

        private boolean simplex() {
            int firstPositiveVariableId = -1;
            for (int i = 1; i <= m && firstPositiveVariableId == -1; i++) {
                if (mat[0][i] > 0) {
                    firstPositiveVariableId = i;
                }
            }
            if (firstPositiveVariableId == -1) {
                return false;
            }
            double maxConstraint = inf;
            int maxConstraintRow = -1;
            for (int i = 1; i <= n; i++) {
                if (mat[i][firstPositiveVariableId] >= 0) {
                    continue;
                }
                double constraint = mat[i][0] / (-mat[i][firstPositiveVariableId]);
                if (maxConstraint > constraint) {
                    maxConstraint = constraint;
                    maxConstraintRow = i;
                }
            }
            if (maxConstraintRow == -1) {
                unbound = true;
                return false;
            }
            pivot(firstPositiveVariableId, maxConstraintRow);
            return true;
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("Maximize\n  ").append(mat[0][0]);
            for (int i = 1; i <= m; i++) {
                if (mat[0][i] == 0) {
                    continue;
                }
                builder.append("+").append(mat[0][i]).append("x").append(i);
            }
            builder.append("\n").append("Constraints\n");
            for (int i = 1; i <= n; i++) {
                builder.append("  ");
                for (int j = 1; j <= m; j++) {
                    if (mat[i][j] == 0) {
                        continue;
                    }
                    builder.append(-mat[i][j]).append("x").append(j).append("+");
                }
                if (builder.length() > 0 && builder.charAt(builder.length() - 1) == '+') {
                    builder.setLength(builder.length() - 1);
                }
                builder.append("<=").append(mat[i][0]).append("\n");
            }

            builder.append("\n").append("Assignment\n");
            for (int i = 1; i <= m; i++) {
                builder.append("  x").append(i).append("=").append(getAssignmentValueForVariable(i)).append("\n");
            }

            return builder.toString();
        }

    }

    static class DualLinearProgramming {
        LinearProgramming lp;
        int n;
        int m;

        public DualLinearProgramming(int n, int m, double prec) {
            this.n = n;
            this.m = m;
            lp = new LinearProgramming(m, n, prec);
        }

        public void setConstraintConstant(int constraintId, double noMoreThan) {
            lp.setTargetCoefficient(constraintId, noMoreThan);
        }

        public void setConstraintCoefficient(int constraintId, int variableId, double c) {
            lp.setConstraintCoefficient(variableId, constraintId, c);
        }

        public void setTargetCoefficient(int variableId, double c) {
            lp.setConstraintConstant(variableId, c);
        }

        public void solve() {
            lp.solve();
        }

        public double minSolution() {
            return lp.maxSolution();
        }

        public boolean isInfeasible() {
            return lp.isUnbound();
        }

        public boolean isUnbound() {
            return lp.isInfeasible();
        }

        public double getAssignmentValueForVariable(int i) {
            if (i + n <= lp.m) {
                return -lp.mat[0][i + n];
            } else {
                return 0;
            }
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (int i = 1; i <= m; i++) {
                double val = getAssignmentValueForVariable(i);
                builder.append("x").append(i).append("=").append(val).append('\n');
            }
            builder.append("min=").append(minSolution());
            return builder.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }
}