#include <bits/stdc++.h>

using namespace std;

const int nmax = 50009;
const int INF = 1000000000;

priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > iq;
vector < pair < int , int > > g[nmax];
int n , m , a , b , c , i , x , y;
int d[nmax];

int main()
{
freopen("dijkstra.in" , "r" , stdin);
freopen("dijkstra.out" , "w" , stdout);

scanf("%d" , &n);
scanf("%d" , &m);

for (i = 1 ; i <= m ; ++i)
{
    scanf("%d" , &a);
    scanf("%d" , &b);
    scanf("%d" , &c);

    g[a].push_back({b , c});
}

for (i = 1 ; i <= n ; ++i)
d[i] = INF;

d[1] = 0;
iq.push({0 , 1});

while (iq.size())
{
    x = iq.top().second;
    iq.pop();

    for (i = 0 ; i < g[x].size() ; ++i)
    {
        y = g[x][i].first;
        c = g[x][i].second;

        if (d[y] > d[x] + c)
        {
            d[y] = d[x] + c;
            iq.push({d[y] , y});
        }
    }
}

for (i = 2 ; i <= n ; ++i)
if (d[i] == INF) printf("0 ");
else printf("%d " , d[i]);
printf("\n");

return 0;
}