from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1
    
    edges = [[] for _ in range(n + 1)]
    for i in range(m):
        a = int(data[idx])
        idx += 1
        b = int(data[idx])
        idx += 1
        c = data[idx]
        idx += 1
        edges[a].append((b, c, i + 1))
        edges[b].append((a, c, i + 1))
    
    # BFS to find a path where first and last characters are different
    visited = {}
    queue = deque()
    initial_state = (1, None, None)
    visited[initial_state] = (None, None, None, None)
    queue.append(initial_state)
    found = False
    result = None
    
    while queue:
        u, first, last = queue.popleft()
        if u == n:
            if first != last:
                # Reconstruct path
                path = []
                current_state = (u, first, last)
                while True:
                    prev_info = visited.get(current_state)
                    if prev_info is None:
                        break
                    prev_node, prev_first, prev_last, edge_id = prev_info
                    if edge_id is not None:
                        path.append(edge_id)
                    current_state = (prev_node, prev_first, prev_last)
                path.reverse()
                print(len(path))
                for edge in path:
                    print(edge)
                found = True
                break
            continue
        
        for v, c, edge_id in edges[u]:
            new_first = first if first is not None else c
            new_last = c
            new_state = (v, new_first, new_last)
            if new_state not in visited:
                visited[new_state] = (u, first, last, edge_id)
                queue.append(new_state)
    
    if not found:
        print(-1)

if __name__ == "__main__":
    main()