import java.io.*;
import java.util.StringTokenizer;

public class Test {
    public static void main(String[] args) {
        InputReader reader = new InputReader();
        int stomachCapacity = reader.readInt();
        int numberOfFoods = reader.readInt();
        String[] foodName = new String[numberOfFoods + 1];
        int[] foodWeight = new int[numberOfFoods + 1];
        int[] foodTaste = new int[numberOfFoods + 1];
        for (int i = 1; i <= numberOfFoods; i++) {
            foodName[i] = reader.readLine();
            foodWeight[i] = reader.readInt();
            foodTaste[i] = reader.readInt();
        }

        int[][] value = new int[numberOfFoods + 1][stomachCapacity + 1];
        for (int r = 1; r <= numberOfFoods; r++) {
            for (int c = 1; c <= stomachCapacity; c++) {
                if (foodWeight[r] <= c) {
                    value[r][c] = getMax(value[r - 1][c], value[r - 1][c - foodWeight[r]] + foodTaste[r]);
                } else {
                    value[r][c] = value[r - 1][c];
                }
            }
        }

        int[] foodEaten = backtrace(value, foodWeight, stomachCapacity, numberOfFoods);

        System.out.println(value[numberOfFoods] [stomachCapacity]);
        for (int i = foodEaten.length - 1; i >= 1; i--) {
            if (foodEaten[i] == 1) {
                System.out.println(foodName[i]);
            }
        }
    }

    private static int[] backtrace(int[][] value, int[] foodWeight, int stomachCapacity, int numberOfFoods) {
        int[] foodEaten = new int[numberOfFoods + 1];
        int r = numberOfFoods;
        int c = stomachCapacity;
        while (r > 0 && c > 0) {
            if (value[r][c] != value[r - 1][c]) {
                foodEaten[r] = 1;
                c = c - foodWeight[r];
            }
            r--;
        }
        return foodEaten;
    }

    private static int getMax(int a, int b) {
        if (a > b) {
            return a;
        } else {
            return b;
        }
    }

    static class InputReader {
        private BufferedReader br;
        private StringTokenizer st;

        InputReader() {
            try {
                br = new BufferedReader(new InputStreamReader(System.in));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String readLine() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int readInt() {
            return Integer.parseInt(readLine());
        }
    }
}