#include<stdio.h>
#include<vector>
#include<utility>
#include<queue>
#include<set>
#include<fstream>
using namespace std;

//http://www.youtube.com/watch?v=x3ndB4l7oNg

#define NMAX 1<<16
#define inf 0x3f3f3f3f

vector< pair<int,int> > G[NMAX];
set < pair<int,int> > H;

int D[NMAX];

void test();
void test_stream();
void dijkstra_set(int source,int N);
void dijkstra_PQ(int source,int N);
void BF_Q(int source,int N);

void test()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    int N,M;
    scanf("%d%d",&N,&M);

    int i,a1,a2,a3;
    for(i=1; i<=M; ++i)
    {
        scanf("%d%d%d",&a1,&a2,&a3);
        G[a1].push_back(make_pair(a2,a3));
    }

    int _source=1;

    //dijkstra_set( _source, N );
    //dijkstra_PQ( _source, N );
    BF_Q(_source, N );

    for(i=_source+1; i<=N; ++i)
        printf("%d ",D[i]!=inf?D[i]:0);
    printf("\n");
}

void test_stream()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    int N,M;
    f>>N>>M;

    int i,a1,a2,a3;
    for(i=1; i<=M; ++i)
    {
        f>>a1>>a2>>a3;
        G[a1].push_back(make_pair(a2,a3));
    }

    int _source=1;

    //dijkstra_set( _source, N );
    //dijkstra_PQ( _source, N );
    BF_Q(_source, N );

    for(i=_source+1; i<=N; ++i)
        g<<(D[i]!=inf?D[i]:0)<<" ";
    g<<"\n";
}

bool V[NMAX];
void dijkstra_set(int source, int N)
{
    unsigned int i;
    for(i=1; i<=N; ++i)
        D[i]=inf,V[i]=0;

    D[source]=0;

    set < pair<int,int> > H;
    H.insert( make_pair( 0,source ) );

    int nod,val,n,dist;
    while( !H.empty() )
    {
        while( !H.empty() && V[ (*H.begin()).second ] )
            H.erase( H.begin() );

        nod=(*H.begin()).second;
        val=D[nod];
        V[nod]=1;

        H.erase( H.begin() );

        for(i=0; i<G[nod].size(); ++i )
        {
            n=G[nod][i].first;
            dist=G[nod][i].second;

            if( val+dist < D[n] )
            {
                D[n]=val+dist;
                H.insert( make_pair( D[n],n ) );
            }
        }
    }
}

class comp
{
  //bool reverse;
  public:
  comp(){};

  bool operator() (const int& lhs, const int&rhs) const
  {
    return D[lhs]>D[rhs];
  }
};

void dijkstra_PQ( int source, int N )
{
    unsigned int i;
    for(i=1; i<=N; ++i)
        D[i]=inf,V[i]=false;

    D[source]=0;

    priority_queue< int, vector<int>, comp > H;

    H.push(source);

    int nod,val,n,edge;
    while( !H.empty() )
    {
        while( !H.empty() && V[ H.top() ] )
            H.pop();

        if( H.empty() ) break;

        nod=H.top();
        val=D[nod];
        V[nod]=1;H.pop();

        for(i=0; i<G[nod].size(); ++i)
        {
            n=G[nod][i].first;
            edge=G[nod][i].second;

            if( val+edge < D[n] )
            {
                D[n]=val+edge;
                H.push(n);
            }
        }
    }
}

void BF_Q(int source,int N)
{
    unsigned int i;
    for(i=1; i<=N; ++i)
        D[i]=inf,V[i]=false;

    queue< int > Q;
    D[source]=0;Q.push(source);V[source]=1;

    int nod,val,n,edge;
    while( !Q.empty() )
    {
        nod=Q.front();
        val=D[nod];
        Q.pop();
        V[nod]=0;

        for(i=0; i<G[nod].size(); ++i)
        {
            n=G[nod][i].first;
            edge=G[nod][i].second;

            if( val+edge < D[n] )
            {
                D[n]=val+edge;
                if( !V[n] )
                {
                    V[n]=1; Q.push(n);
                }
            }
        }
    }
}

int main()
{
    test(); // debug purpose
    //test_stream();
    return 0;
}