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

using namespace std;

#define NMAX 50010
#define INF (1<<30)
#define GKnoten (*it).first
#define GAbstand (*it).second
#define PII pair < int , int >

int N,M;
int Abstand[NMAX];

bool Gebraucht[NMAX];

vector < PII > G[NMAX];

priority_queue < PII , vector < PII > , greater < PII > > 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(0,1));

    while(!PQ.empty())
    {
        int Knoten = PQ.top().second;
        PQ.pop();

        if(Gebraucht[Knoten])
            continue;
        Gebraucht[Knoten] = true;

        for(vector < PII > :: iterator it = G[Knoten].begin(); it != G[Knoten].end(); ++ it )
            if(Abstand[GKnoten] > Abstand[Knoten] + GAbstand)
            {
                Abstand[GKnoten] = Abstand[Knoten] + GAbstand;
                PQ.push(make_pair(Abstand[GKnoten],GKnoten));
            }
    }
}

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

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

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