Rust program sometimes gives inconsistent results

I am working on the first part of the 9th day of Advent of Code in Rust and am facing some weird problem. I wrote the following code, which usually works, but about 10% of the time it gives the wrong answer.

extern crate permutohedron;

use std::fs::File;
use std::io::{BufRead, BufReader};
use std::collections::HashMap;
use std::rc::Rc;

use permutohedron::LexicalPermutation;

fn get_distance(cities: &[Rc<String>], paths: &HashMap<(Rc<String>, Rc<String>), i64>) -> i64 {
    cities.iter().fold((0, None), |(sum, last_city), city| {
        (last_city.map_or(0, |last_city| {
            sum + *paths.get(&(last_city, city.clone())).unwrap()
        }), Some(city.clone()) )
    }).0
}

fn main() {

    let file = File::open("input_9.txt").unwrap();
    let file = BufReader::new(file);

    let mut paths = HashMap::new();
    let mut cities = HashMap::new();

    for line in file.lines() {
        let line = line.unwrap();
        let mut words = line.split(' ');
        let from = words.nth(0).unwrap();
        let to = words.nth(1).unwrap();

        if !cities.contains_key(from) {
            cities.insert(from.to_owned(), Rc::new(from.to_owned()));
        }
        if !cities.contains_key(to) {
            cities.insert(to.to_owned(), Rc::new(to.to_owned()));
        }

        let from = cities.get(from).unwrap();
        let to = cities.get(to).unwrap();

        let dist = words.nth(1).unwrap().parse::<i64>().unwrap();
        paths.insert((from.clone(), to.clone()), dist);
        paths.insert((to.clone(), from.clone()), dist);
    }

    let mut cities_perm: Vec<_> = cities.values().map(|k| k.clone()).collect();

    let mut min_path = None;
    loop {
        let dist = get_distance(&cities_perm, &paths);

        min_path = Some(min_path.map_or(dist, |v|
            *[v, dist].iter().min().unwrap()
        ));

        if !cities_perm.next_permutation() { break }
    }

    println!("{}", min_path.unwrap());

}

      

        
        
        
      

    

I run it with cargo run

and never change the file input_9.txt

, so I see no reason why it should give different answers. I also tried building it and then running the executable that it built directly, for example ./target/debug/day_9

, and the same thing happens. I have noticed that it often leads to incorrect results more often after its creation rather than later.

I usually get 141

which is correct. However, sometimes it prints something like 210

, 204

or 155

. Why is this happening?

Here's the entrance to the program if it helps you: https://pastebin.com/XJzsMy5A