#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#define N_MAX 50010
#define INF 2000000000
#define mp make_pair
#define pb push_back
using namespace std;
vector < pair<int,int> > G[N_MAX];
queue <int> Q;
int D[N_MAX],N;
bool pus[N_MAX];
inline void Write_Sol(int N)
{
    for (int i=2;i<=N;++i)
        if (D[i]==INF) printf("0 ");
                else printf("%d ",D[i]);
    printf("\n");
}
inline void Solve()
{
    while (!Q.empty())
    {
        int Nod=Q.front(), Cost=D[Nod];
        Q.pop(); pus[Nod]=false;
        for (vector < pair <int,int> > :: iterator it=G[Nod].begin();it!=G[Nod].end();++it)
        {
            int nod=(*it).first, cost=(*it).second;
            if (D[nod] > Cost + cost)
                {
                    D[nod]=Cost + cost;
                    if (!pus[nod]) {Q.push(nod); pus[nod]=true;}
                }
        }
    }
}
inline void Load_Data(int &N)
{
    int M,x,y,c;
    scanf("%d%d",&N,&M);
    for (int i=1;i<=M;++i)
        scanf("%d%d%d",&x,&y,&c), G[x].pb(mp(y,c));
    for (int i=1;i<=N;++i) {D[i]=INF; pus[i]=false;}
    D[1]=0; pus[1]=true; Q.push(1);
}
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    Load_Data(N);
    Solve();
    Write_Sol(N);
    fclose(stdin); fclose(stdout);
    return 0;
}