//Vasilut
//Implementare Dijkstra cu ajutorul lui BMF cu queue

#include<fstream>
#include<vector>
#include<queue>


#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define NN 50001
#define f first
#define s second


using namespace std;
ofstream out("dijkstra.out");

int n,m;
vector<pair<int,int > > G[NN];
vector<int>dist;
queue<int>Q;

void read();
void Dijkstra();
void write();

int main()
{
    read();
    Dijkstra();
    write();
    return 0;
}

void read()
{
    ifstream in("dijkstra.in");
    in>>n>>m;
    for(int x,y,c; m ;--m)
    {
        in>>x>>y>>c;
        G[x].pb(mp(y,c));
    }
}

void write()
{
        for(int i=2;i<=n;i++)
            if(dist[i] == INF )
                out<<0<<" ";
                else
                out<<dist[i]<<" ";
}


void Dijkstra()
{
    dist.resize(n+1,INF);
    dist[1]=0;
    Q.push(1);
    while(!Q.empty())
    {
        int k=Q.front();

            for(int i=0; (int) i<G[k].size(); ++i)
            {
                if(dist[G[k][i].f] > dist[k] + G[k][i].s )
                {
                   dist[G[k][i].f]=dist[k] + G[k][i].s;
                   Q.push(G[k][i].f);
                }

            }
            Q.pop();
    }
}