#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 50010
#define INF 0x3f3f3f3f
#define PKnoten first
#define PAbstand second

int N,M;
int Abstand[NMAX];

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

priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > PQ;

void Scannen()
{
    freopen("dijkstra.in","r",stdin);

    scanf("%d%d",&N,&M);
    for(int i=1,x,y,z;i<=M;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back(make_pair(y,z));
    }
}

void Losen_Dijkstra()
{
    for(int i=2;i<=N;Abstand[i++]=INF);
    PQ.push(make_pair(1,0));

    while(!PQ.empty())
    {
        int _Knoten = PQ.top().PKnoten;
        int _Abstand = PQ.top().PAbstand;
        PQ.pop();

        for(vector < pair < int , int > > :: iterator it = G[_Knoten].begin(); it != G[_Knoten].end(); ++ it )
            if(Abstand[(*it).PKnoten] > _Abstand + (*it).PAbstand)
            {
                Abstand[(*it).PKnoten] = _Abstand + (*it).PAbstand;
                PQ.push(make_pair( (*it).PKnoten , Abstand[(*it).PKnoten]) );
            }
    }
}

void Drucken()
{
    freopen("dijkstra.out","w",stdout);

    for(int i=2;i<=N;i++)
        printf("%d ",(Abstand[i] != INF)?(Abstand[i]):(Abstand[i] - INF));
}

int main()
{
    Scannen();
    Losen_Dijkstra();
    Drucken();
    return 0;
}