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

using namespace std;

#define pb push_back

const int NMAX = 50000;
const int INF = 1000000000;

int n, m;
int cost[NMAX + 1];
vector< pair<int, int> > v[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);
        v[from].pb({co, to});
    }

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

    st.insert({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 < v[node].size(); i++)
        {
            if(cost[v[node][i].second] > c + v[node][i].first)
            {
                cost[v[node][i].second] = c + v[node][i].first;
                st.insert({cost[v[node][i].second], v[node][i].second});
            }
        }
    }

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