package graph;

import static java.util.Arrays.fill;

/**
 * Created by dmitry_boltacev on 16.03.17.
 */
public class Main {


    static int array[][] = { {1, 2, 1},
                          {2, 3, 1},
                          {2, 5, 3},
                          {1, 3, 2},
                          {3, 5, 1},
                          {2, 4, 1},
                          {5, 6, 2}};

//    static int array[][] = { {1, 3, 1}, {1, 2, 10}, {2, 4, 5}, {3, 6, 1}, {1, 5, 1}, {5, 7, 20}, {6, 7, 1}};
//    static int array[][] = { {1, 3, 1}, {1, 2, 10}, {1, 4, 10}, {1, 5, 20}, {2, 3, 1}, {2, 4, 1}, {2, 5, 1}, {3, 4, 1}, {3, 5, 1}, {4, 5, 1}};


    static int n = countVertex(array); // вершины
    static int m = array.length;// ребра

    public static void main(String[] args) {

        System.out.println(n);

        int matrix[][] = new int[n][n];

        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                matrix[i][j] = 0;
            }
        }

        for (int i = 0; i < m; i ++) {
            int l = array[i][0] - 1; // 0
            int k = array[i][1] - 1; // 1
            matrix[l][k] = array[i][2];
            matrix[k][l] = array[i][2];
        }

        int way[] = new int [100];

        int model = deykstra(matrix); //эталон

        int countWays = 0;

        for (int i = 0; i < m; i ++) {
            int l = array[i][0]-1; // 0
            int k = array[i][1]-1; // 1
            matrix[l][k] -= array[i][2];
            matrix[k][l] -= array[i][2];

            way[i] = deykstra(matrix);

            matrix[l][k] = array[i][2];
            matrix[k][l] = array[i][2];

            if(way[i] != model) {
                countWays++;
            }
        }

        System.out.println(countWays);


        for (int i = 0; i < m; i ++) {
            if (way[i] != model)
                System.out.print(i + 1 + " ");
        }

    }

    private static int countVertex(int [][]array) {
        int v = 0;

        for (int i = 0; i < array.length; i++)
            if (array[i][1] > array[i][0])
                v = array[i][1];
        return v;
    }

    private static int deykstra(int matrix[][]) {

        int d[] = new int[n];  // минимальное расстояние
        int v[] = new int[n]; // посещенные вершины

        int temp;
        int min, minindex;

        for (int i = 0; i < n; i++) {
            d[i] = 10000;
            v[i] = 1;
        }

        d[0] = 0;

        do {
            minindex = 10000;
            min = 10000;
            for (int i = 0; i < n; i++) {
                if ((v[i]) == 1 && (d[i] < 10000)) {
                    min = d[i];
                    minindex = i;
                    break;
                }
            }

            if (minindex != 10000)
            {
                for (int i = 0; i < n; i++)
                {
                    if (matrix[minindex][i] > 0)
                    {
                        temp = min + matrix[minindex][i];
                        if (temp < d[i])
                            d[i] = temp;
                    }
                }
                v[minindex] = 0;
            }
        } while (minindex < 10000);

        return d[n - 1];

    }

}