#include <vector>
#include <cstdio>
#include <string.h>
#include <queue>

using namespace std;

#define Nmax 50010
#define inf 0x3f3f3f3f
vector <pair<int,int> > ad[Nmax] ;
int n , m , x , y , c ;
int D[Nmax];
bool viz[Nmax];

void Dijkstra ( int start )
{
    memset(D, inf, sizeof(D));
    memset(viz, 0, sizeof(viz));
    D[1] = 0;
    viz[1] = true;
    queue<int> Q;
    Q.push(1);

    while (!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        viz[nod] = false;
        for (int i = 0; i < ad[nod].size(); ++i)
            if (D[nod] + ad[nod][i].second < D[ad[nod][i].first])
                {
                    D[ad[nod][i].first] = D[nod] + ad[nod][i].second;
                    if ( !viz[ad[nod][i].first] )
                    {
                        Q.push(ad[nod][i].first) ;
                        viz[ad[nod][i].first]=true;
                    }
        }
    }
}

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

    scanf("%d %d",&n,&m);
    for ( int i = 1 ; i <= m ; i++ )
    {
        scanf("%d %d %d",&x,&y,&c);
        ad[x].push_back(make_pair(y,c));
        //ad[y].push_back(make_pair(x,c));
    }
    Dijkstra(1);
    for ( int i = 2 ; i <= n ; ++i )
    {
        if ( D[i] == 0x3f3f3f3f ) D[i] = 0 ;
        printf("%d ",D[i]);
    }
}