#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 T[Nmax];

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

    while (!Q.empty()) {
        int nod = Q.front(); Q.pop();

        T[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 (!T[ad[nod][i].first]) Q.push(ad[nod][i].first), T[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]);
    }
}