Instance: An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 0$.
Question: Does there exist an $s-t$ path in $G$, such that the path intersects at most $k$ triangles? (For this problem a path is said to intersect a triangle if the path contains at least one edge from the triangle.)
Assume there are no self-edges in $G$.
For each edge between node $v_i$ and $v_j$ in $G$, let $E[i,j]=1$, and $E[i,j]=0$ if there is no edge. Compute $n\times n$ matrix $C[i,j]=\sum_{k=1}^n E[i,k]\cdot E[k,j]$, which gives the number of two-hop paths between each pair of nodes $v_i$ and $v_j$. Then for edge between $v_i$ and $v_j$ in $G$ compute $D[i,j]=E[i,j]\cdot C[i,j]$ otherwise set $D[i,j]=\infty$, which gives the number of triangles the edge is part of (or infinity if there is no edge). The matrix multiplication needed to compute $C$ costs $O(n^3)$ (could be computed faster depending on sparsity of $G$).
Now compute $n\times n$ matrix $A$, such that $A[i,j]=\min(D[i,j],\min_k(D[i,k]+D[k,j]-E[i,j]))$. $A$ is all shortest-paths in $D$ of length up to two augmented to account for paths that go along two edges of some triangle.
Now just compute the shortest path between $v_i$ and $v_j$ in $G$ on a new graph of which $A$ is the (weighted) adjacency matrix using Dijkstra (since all edge-weights are positive) i.e. and determine if $A^*[i,j]\leq k$, where $A^*$ is the closure over the tropical semiring (which gives the distance matrix).
