#include<cstdio>
#include<vector>
#include<set>

using namespace std;

#define pb push_back

const int NMAX = 50010;
const int INF = 1000000000;

int n, m;
int cost[NMAX + 1];
vector< int > vec[NMAX + 1], pr[NMAX + 1];
set< pair<int, int> > st;

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

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

    int from, to, co;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &from, &to, &co);
        vec[from].pb(to);
        pr[from].pb(co);
    }

    for(int i = 2; i <= n; i++)
    {
        cost[i] = INF;
    }

    st.insert(make_pair(0, 1));
    int c, node;
    while(st.empty() != true)
    {
        c = (*st.begin()).first;
        node = (*st.begin()).second;

        st.erase(*st.begin());
        for(int i = 0; i < vec[node].size(); i++)
        {
            if(cost[vec[node][i]] > c + pr[node][i])
            {
                cost[vec[node][i]] = c + pr[node][i];
                st.insert(make_pair(cost[vec[node][i]], vec[node][i]));
            }
        }
    }

    for(int i = 2; i <= n; i++)
    {
        printf("%d ", cost[i]);
    }
}