#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

// Using type aliases for clarity and brevity
using VI = vector<int>;         // Vector of integers
using VC = vector<char>;        // Vector of characters
using PII = pair<int, int>;     // Pair of integers
// Tuple to represent an edge in the adjacency list: {neighbor_vertex, edge_label, edge_index}
template<typename T1, typename T2, typename T3>
using Tuple3 = tuple<T1, T2, T3>; 

const int MAXN_glob = 100005; // Maximum number of vertices + 1
const int MAXM_glob = 200005; // Maximum number of edges + 1

// Adjacency list representation of the graph
// adj_glob[u] stores a list of tuples {v, label, edge_idx} for edges connected to vertex u
vector<Tuple3<int, char, int>> adj_glob[MAXN_glob]; 
// Array to store edge information (u, v, label) indexed by edge ID (1 to M)
// This allows quick lookup of edge label given its index
Tuple3<int, int, char> edge_info_glob[MAXM_glob + 1]; 
int N_glob, M_glob; // Global variables for number of vertices N and edges M


/**
 * @brief Checks if a sequence of characters forms a palindrome.
 * 
 * @param labels The vector of characters representing the sequence.
 * @return true if the sequence is a palindrome, false otherwise.
 */
bool is_palindrome(const VC& labels) {
    int k = labels.size();
    // An empty string or a string with one character is considered a palindrome.
    if (k <= 1) return true; 
    // Compare characters from the beginning and end moving inwards.
    for (int i = 0; i < k / 2; ++i) {
        if (labels[i] != labels[k - 1 - i]) {
            return false; // If any pair doesn't match, it's not a palindrome.
        }
    }
    return true; // All pairs matched, it's a palindrome.
}


int main() {
    // Use fast I/O operations.
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read the number of vertices N and edges M from input.
    cin >> N_glob >> M_glob;

    // Read M edges from input and populate the adjacency list and edge info array.
    for (int i = 1; i <= M_glob; ++i) {
        int u, v;
        char c;
        cin >> u >> v >> c; // Read vertices u, v and edge label c.
        // Add edge to adjacency list for both u and v (since it's an undirected graph).
        adj_glob[u].emplace_back(v, c, i);
        adj_glob[v].emplace_back(u, c, i);
        // Store edge info (u, v, label) associated with edge index i.
        edge_info_glob[i] = make_tuple(u, v, c);
    }

    // Perform Breadth-First Search (BFS) starting from vertex 1 to find a shortest path to vertex N.
    queue<int> q; // Queue for BFS
    VI dist(N_glob + 1, -1); // distance[v] stores shortest distance from vertex 1 to v. Initialized to -1 (unvisited).
    // parent[v] stores {previous_node, edge_index_used} to reach v in the shortest path from 1.
    vector<PII> parent(N_glob + 1, {-1, -1}); 

    q.push(1); // Start BFS from vertex 1.
    dist[1] = 0; // Distance from source to itself is 0.

    int final_node = -1; // Variable to confirm if vertex N was reached.

    // BFS loop
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // If we reached the target vertex N, stop BFS.
        if (u == N_glob) {
            final_node = N_glob;
            break; 
        }

        // Explore neighbors of vertex u.
        for (auto& edge : adj_glob[u]) {
            int v = get<0>(edge); // Neighbor vertex
            int edge_idx = get<2>(edge); // Index of the edge (u, v)
            // If neighbor v has not been visited yet (distance is -1).
            if (dist[v] == -1) { 
                dist[v] = dist[u] + 1; // Update distance to v.
                parent[v] = {u, edge_idx}; // Set parent of v for path reconstruction.
                q.push(v); // Add v to the queue to visit later.
            }
        }
    }
    
    // After BFS, check if vertex N was reachable from vertex 1.
    if (final_node == -1) {
        // The problem guarantees the graph is connected, so N should always be reachable if N >= 2.
        // Output -1 if N is unreachable (this should theoretically not happen based on constraints).
        cout << -1 << endl;
        return 0;
    }

    // Reconstruct the shortest path from 1 to N using the parent pointers.
    VI path_v; // Stores the sequence of vertices in the path.
    VI path_e; // Stores the sequence of edge indices used in the path.
    VC path_l; // Stores the sequence of edge labels along the path.
    int curr = N_glob; // Start reconstruction from the target vertex N.
    // Trace back parents until we reach the start vertex 1.
    while (curr != 1) {
        // Defensive check for errors during reconstruction.
        if (parent[curr].first == -1 && curr != 1) {
             cerr << "Error during path reconstruction: Parent indicates start node prematurely." << endl; 
             cout << -1 << endl; return 0; 
        }
        int p_node = parent[curr].first; // Previous node in the path.
        int edge_idx = parent[curr].second; // Index of the edge used to reach curr from p_node.
        path_e.push_back(edge_idx); // Add edge index to path list.
        
        // Retrieve the label of the edge using the stored edge info.
        char label = get<2>(edge_info_glob[edge_idx]);
        path_l.push_back(label); // Add label to path list.

        path_v.push_back(curr); // Add current vertex to path list (will be reversed).
        curr = p_node; // Move to the previous vertex.
    }
    path_v.push_back(1); // Add the starting vertex 1 to the path list.
    
    // The path was reconstructed backwards (from N to 1), so reverse the sequences.
    reverse(path_v.begin(), path_v.end()); // path_v now stores vertices 1...N
    reverse(path_e.begin(), path_e.end()); // path_e now stores edge indices along 1...N
    reverse(path_l.begin(), path_l.end()); // path_l now stores labels along 1...N

    // Check if the label sequence of the found shortest path is a palindrome.
    if (!is_palindrome(path_l)) {
        // If it's not a palindrome, this path is a valid solution. Output it.
        cout << path_e.size() << endl; // Output path length (number of edges).
        for(int edge_idx : path_e) {
            cout << edge_idx << endl; // Output each edge index on a new line.
        }
        return 0; // Solution found, terminate program.
    }

    // If the shortest path is a palindrome, we need to find a different path.
    // Strategy: Try modifying the shortest path by inserting a small cycle (u -> w -> u).
    int k = path_e.size(); // Length of the shortest path.
    // Iterate through each vertex v_i on the shortest path (vertices are indexed 0 to k).
    for (int i = 0; i < path_v.size(); ++i) { 
        int u = path_v[i]; // Current vertex v_i on the path.
        
        // Iterate through all edges incident to vertex u.
        for (auto& edge : adj_glob[u]) { 
            // int w = get<0>(edge); // Neighbor vertex w, not strictly needed here.
            char c_prime = get<1>(edge); // Label of the edge (u, w).
            int e_prime_idx = get<2>(edge); // Index of the edge (u, w).

            // Construct the label sequence for the new path P' which includes the cycle u -> w -> u.
            // The new path essentially goes 1... -> u -> w -> u -> ...N.
            VC new_path_l; // Vector to store the labels of the modified path.
            new_path_l.reserve(k + 2); // Reserve space for efficiency (length will be k+2).

            // Part 1: Add labels from the original path before vertex v_i (edges e_1 to e_i).
            // These correspond to labels path_l[0] through path_l[i-1].
            for (int j = 0; j < i; ++j) {
                new_path_l.push_back(path_l[j]);
            }
            // Part 2: Insert the labels corresponding to the cycle u -> w -> u.
            // Both traversals use the same edge (u, w), so the label c_prime appears twice.
            new_path_l.push_back(c_prime);
            new_path_l.push_back(c_prime);
            // Part 3: Add labels from the original path starting from vertex v_i (edges e_{i+1} to e_k).
            // These correspond to labels path_l[i] through path_l[k-1].
            for (int j = i; j < k; ++j) {
                new_path_l.push_back(path_l[j]);
            }
            
            // Check if the modified path P' has a non-palindromic label sequence.
            if (!is_palindrome(new_path_l)) {
                 // If non-palindromic, construct its edge index sequence.
                 VI new_path_e; // Vector to store edge indices of the modified path.
                 new_path_e.reserve(k + 2); // Reserve space for efficiency.

                 // Edges corresponding to Part 1 (before index i).
                 for(int j=0; j<i; ++j) {
                     new_path_e.push_back(path_e[j]);
                 }
                 // Edges corresponding to Part 2 (the cycle u -> w -> u).
                 // Edge index e_prime_idx is used twice.
                 new_path_e.push_back(e_prime_idx); 
                 new_path_e.push_back(e_prime_idx); 
                 // Edges corresponding to Part 3 (from index i onwards).
                 for(int j=i; j < k; ++j) {
                      new_path_e.push_back(path_e[j]);
                 }
                 
                 // Check if the new path length exceeds the constraint 2*N.
                 // The length is k+2. Since k <= N-1 (shortest path), k+2 <= N+1.
                 // For N >= 1, N+1 <= 2N. Constraint is always satisfied if N>=1. Problem states N>=2.
                 if (new_path_e.size() > 2 * N_glob) {
                    // This condition should technically not be met given the logic above, but included as a safeguard.
                    continue; // Skip if path somehow exceeds length limit.
                 }

                 // Output the resulting path edge indices.
                 cout << new_path_e.size() << endl; // Output path length k+2.
                 for(int edge_idx : new_path_e) {
                     cout << edge_idx << endl; // Output each edge index.
                 }
                 return 0; // Solution found, terminate program.
            }
        }
    }

    // If the program reaches this point, it means the shortest path was a palindrome,
    // and inserting any single cycle u -> w -> u at any vertex u on the path
    // also resulted in a palindrome. In this case, we conclude no suitable path
    // was found meeting the criteria (non-palindromic, length <= 2N).
    cout << -1 << endl;

    return 0;
}