I would rarely cross a border twice just to save a few minutes (dubious) or to be on a better road. But I would have detoured and gone on the more major NB highways. If I'm ever on a long trip in some place I'm not too familiar with, I try to stay on major roads and I have absolutely zero patience for dirt or gravel roads. I'm not afraid to just turn around and cut my losses, when I get surprised by a road not being paved. Google should do a better job of pointing out routes with unpaved roads in my opinion. This has caught me off guard out west a few times as well.