On the outbound you do not have to change terminals. Your flight from Madison will arrive at the A gates and most likely the flight to Montreal will also leave from A. All the international flights leave from the same gates that mainline service leaves from, there is no seperate international terminal. The maximum amount of time it has ever taken for me to change planes in DTW was about 15 minutes (an A to C change). Officially, you need to be onboard the Montreal flight 30 minutes prior to depature, but if you are connecting, you really just need to get to the flight in a timely manner after your MSN flight lands.

In short: I would recommend you book this, it will not be a very difficult connection.