#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>
#include<vector>
using namespace std;

struct muchie
{
    int vec,cost;
};

vector <muchie> G[50000+10];
int viz[50000+10],d[50000+10];

inline void dijkstra()
{
    memset(d,0x3f,sizeof(d));
    set<pair<int,int> > S;

    d[1]=0;
    S.insert(make_pair(0,1));
    while(!S.empty())
    {
        int nod=S.begin()->second,cost=S.begin()->first;
        S.erase(S.begin());
        for(vector<muchie>::iterator it=G[nod].begin(),stop=G[nod].end();it<stop;++it)
        {
            if(d[it->vec]>cost+it->cost)
            {
                d[it->vec]=cost+it->cost;
                S.insert(make_pair(d[it->vec],it->vec));
            }
        }
    }

}
int main()
{
    freopen("dijkstra.in","rt",stdin);
    freopen("dijkstra.out","wt",stdout);

    int n,m;

    cin>>n>>m;

    for(int i=1;i<=m;++i)
    {
        int a,b,c;
        cin>>a>>b>>c;
        G[a].push_back((muchie){b,c});
    }
    dijkstra();

    for(int i=2;i<=n;++i)
        cout<<d[i]<<' ';
    putchar('\n');

    return 0;
}
/*
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define MAXN 50100
#define INF 1000000000

int N, M, d[MAXN]; vector<int> G[MAXN], C[MAXN];
set< pair<int, int> > T;

void solve(void)
{
    int i, j, k, val, x;

    for(i = 2; i <= N; i++) d[i] = INF;
    T.insert( mp(0, 1) );

    while( T.size() > 0 )
    {
        val = (*T.begin()).first, x = (*T.begin()).second;
        T.erase(*T.begin());
        for(i = 0; i < G[x].size(); i++)
         if(d[ G[x][i] ] > val + C[x][i] )
            d[ G[x][i] ] = val + C[x][i], T.insert(mp(d[G[x][i]],G[x][i]));
    }
}

int main(void)
{
    freopen("dijkstra.in", "rt", stdin);
    freopen("dijkstra.out", "wt", stdout);

    int i, a, b, c;

    scanf("%d %d\n", &N, &M);

    for(i = 1; i <= M; i++)
        scanf("%d %d %d\n", &a, &b, &c), G[a].pb(b), C[a].pb(c);

    solve();

    for(i = 2; i <= N; i++)
        printf("%d ", d[i] == INF ? 0 : d[i]);

    return 0;
}





*/